[백준] 18258번 : 큐 2 - JAVA [자바]

 
www.acmicpc.net/problem/18258

18258번: 큐 2

 

---

• 문제

 

 

 

 

큐에 대한 원리만 알고 있어도 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

단계별로 풀어보기 큐와 덱 카테고리 첫 문제다.

 

이 번 문제같은 경우 자료구조를 한 번쯤 접해봤거나 큐에 대한 개념이 있다면 쉽게 풀 수 있는 문제다.

잠깐 큐에 대해 설명하자면 큐 자료구조의 경우 '선입선출' 자료구조로 말 그대로 먼저 들어간 요소가 먼저 나오는 방식이다. 쉽게 생각해서 놀이기구를 타기위해 줄서있는 모습을 생각하면 된다.

 

큐에 대한 자세한 내용과 구현은 아래 글을 참고하시길 바란다.

자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기

 

 

만약 연결리스트로 구현 된 것을 보고싶다면 아래 링크를 참고하면 된다.

자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기

 

 

 

 

잠깐 덱에 관해서도 살짝 언급하고 가자면, 큐는 단방향으로 요소(데이터)가 들어가는 방향과 나오는 방향이 다르다.

반면 덱은 Double-ended Queue 의 줄임말인데, 말 그대로 양방향의 지점이 있는 큐다. 설명으로는 어려울테니 컨셉이 어떤지 그림으로 보고가도록 하자.

 

 

 

 

 

 

 

그리고 이 문제를 풀 떄 중요한 점이 있다.

 

물론 대개는 구현해서 풀겠지만, 라이브러리를 사용한다는 가정하에 C++같은 경우 queue 라이브러리에는 가장 맨 뒤에 있는 요소를 반환하는 back() 메소드가 있지만, Java의 경우는 Queue 인터페이스로 선언하여 라이브러리를 사용할 경우 back() 과 같은 역할을 하는 메소드는 없다. (맨 앞의 원소를 반환하는 것은 peek() 메소드가 있다.)

 

즉, 예로들어 아래와 같이 쓸 경우 맨 뒤의 원소를 반환하는 메소드가 없다는 것이다.

Queue<Integer> q = new LinkedList<>();
Queue<Integer> q = new ArrayDeque<>();

 

쉽게 말해 Queue 및 Queue의 부모 인터페이스인 Collection으로 선언하는 경우 (Queue<Integer> q 와 같이) 뒤의 원소를 꺼내올 수 있는 방법이 없다.

 

아래 이미지를 참고하면 된다.

 

 

 

 

그러면 어떻게 해야 할까?

 

일단 해결책으로 여러가지가 있지만 라이브러리를 이용하는 방법 중 대표적으로 활용 할 수 있는 방법들을 소개하자면 이렇다.

 

/*
 * 방법 1
 * LinkedList는 Deque(Queue를 상속받고 있음)도 구현하고 있기 때문에
 * LinkedList로 선언해주어 사용 할 수 있다.
 */
LinkedList<Integer> q = new LinkedList<>();
q.offer();	// push
q.pop();	// pop
q.size();	// size
q.isEmpty();	// empty
q.peek();	// front
q.peekLast();	// back


/*
 * 방법 2
 * Deque 인터페이스로 선언한 뒤
 * LinkedList나 ArrayDeque로 생성하여 이용 할 수 있음
 */
Deque<Integer> q = new LinkedList<>();
Deque<Integer> q = new ArrayDeque<>();

// 메소드는 동일함
q.offer();	// push
q.pop();	// pop
q.size();	// size
q.isEmpty();	// empty
q.peek();	// front
q.peekLast();	// back

 

 

이렇게 여러 생성 방법이 있으니 라이브러리를 이용할 경우 위에서 각자가 편한 선언 방식을 쓰면 된다.

 

 

또는 마지막 방법으로는 직접 구현하는 것이다. 이 방법은 필자가 위에 참고하라는 글 중 배열 큐(ArrayQueue)에 모든 원리가 다 들어가 있으니 달리 설명하진 않겠다. 대신 주석으로 달아놓도록 하겠다.

 

참고로 ArrayList로도 큐처럼 사용 할 수는 있지만 삽입 삭제가 많아서 효율이 LinkedList 보다 안좋다. 필자가 테스트 해보니까 시간초과가 난다.

 

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

라이브러리를 이용한 방법 두 개(LinkedList, ArrayDeque)를 사용한 것과 직접 구현한 방식을 비교해보고자 한다.

 

이 번 문제의 경우 시간 제한이 은근 빡빡하기에 모두 BufferedReader로 입력받을 것이고, 출력은 모든 출력 문자열을 StringBuilder 로 묶어준 다음에 한 번에 출력하는 방식을 사용할 것이다. (여러분의 편의에 따라 BufferedWriter로 써도 무방하다.)

 

1 . LinkedList 방식

2. ArrayDeque 방식

3. 직접 구현 방식

 

 

 

 

---

• 풀이

- 방법 1 : [LinkedList 방식]

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		Deque<Integer> q = new LinkedList<>();
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer command;
		
		while(N-- > 0) {
			command = new StringTokenizer(br.readLine(), " ");	// 문자열 분리 
			
			switch(command.nextToken()) {	
			
			case "push":
				// offer는 큐의 맨 뒤에 요소를 추가한다.
				q.offer(Integer.parseInt(command.nextToken()));	
				break;
			
			case "pop" :
				/*
				 *  poll은 가장 앞에 있는 요소를 삭제하며
				 *  삭제할 원소가 없을 경우 예외를 던지는 것이 아닌 null을 반환한다.
				 */
				Integer item = q.poll();	
				if(item == null) {
					sb.append(-1).append('\n');
				}
				else {
					sb.append(item).append('\n');
				}
				break;
				
			case "size":	
				sb.append(q.size()).append('\n');
				break;
				
			case "empty":
				if(q.isEmpty()) {
					sb.append(1).append('\n');
				}
				else {
					sb.append(0).append('\n');
				}
				break;
				
			case "front":
				// peek()은 큐에 꺼낼 요소가 없을 경우 null을 반환한다.
				Integer ite = q.peek();
				if(ite == null) {
					sb.append(-1).append('\n');
				}
				else {
					sb.append(ite).append('\n');
				}
				break;
				
			case "back":
				// peekLast()은 큐에 꺼낼 요소가 없을 경우 null을 반환한다.
				Integer it = q.peekLast();	 
				if(it == null) {
					sb.append(-1).append('\n');
				}
				else {
					sb.append(it).append('\n');
				}
				break;
			}
		}
		System.out.println(sb);
	}
}

 

 

 

LinkedList 라이브러리를 이용한 가장 기본적인 방법이다.

Deque<Integer> q = new LinkedList<>(); 대신 LinkedList<Integer> q = new LinkedList<>(); 로 선언해주어도 무방하다. 

 

 

 

---

- 방법 2 : [ArrayDeque 방식]

 

 

 

양방향으로 접근이 가능한 큐다. 흔히 '덱'이라고 부른다.

굳이 LinkedList와 비교하는 이유는 LinkedList는 노드(객체)를 서로 참조하여 연결하는 방식인 반면에 ArrayDeque는 내부에 Object[] 배열을 두어 해당 배열에 데이터를 관리하기 때문이다.

 

즉, 같은 덱 또는 큐라고 할지라도 구현 방식에는 여러가지가 있다는 것을 알려주고자 했다.

아직 자료구조를 구현해본 경험이 없다면 어려운 이야기일 수 있지만, 이후 배열로 구현하느냐, 연결리스트로 구현하느냐의 차이가 꽤 크다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		Deque<Integer> q = new ArrayDeque<>();
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer command;
		
		while(N-- > 0) {
			command = new StringTokenizer(br.readLine(), " ");	// 문자열 분리 
			
			switch(command.nextToken()) {	
			
			case "push":
				// offer는 큐의 맨 뒤에 요소를 추가한다.
				q.offer(Integer.parseInt(command.nextToken()));	
				break;
				
			case "pop" :
				/*
				 *  poll은 가장 앞에 있는 요소를 삭제하며
				 *  삭제할 원소가 없을 경우 예외를 던지는 것이 아닌 null을 반환한다.
				 */
				Integer item = q.poll();	
				if(item == null) {
					sb.append(-1).append('\n');
				}
				else {
					sb.append(item).append('\n');
				}
				break;
				
			case "size":	
				sb.append(q.size()).append('\n');
				break;
				
			case "empty":
				if(q.isEmpty()) {
					sb.append(1).append('\n');
				}
				else {
					sb.append(0).append('\n');
				}
				break;
				
			case "front":
				// peek()은 큐에 꺼낼 요소가 없을 경우 null을 반환한다.
				Integer ite = q.peek();
				if(ite == null) {
					sb.append(-1).append('\n');
				}
				else {
					sb.append(ite).append('\n');
				}
				break;
				
			case "back":
				// peekLast()은 큐에 꺼낼 요소가 없을 경우 null을 반환한다.
				Integer it = q.peekLast();	 
				if(it == null) {
					sb.append(-1).append('\n');
				}
				else {
					sb.append(it).append('\n');
				}
				break;
			}
		}
		System.out.println(sb);
	}
}

 

 

만약 지금 다룬 큐나 덱 내용에 대해 어렵다면 기본적인 자료구조 개념부터 배우고 오시는게 오히려 이후 문제들을 풀 때 훨씬 편할 것이다...

 

 

 

 

---

- 방법 3 : [직접 구현 방식]

 

 

 

 

필자가 참고하라는 글을 보셨다면 알겠지만, 구현 자체는 그리 어렵지 않다.

오히려 이 번 문제에서는 특정 기능만 요구하고 입력의 범위도 주어져 있기 때문에 매우 간소화 해서 풀어낼 수 있다. 고려해야 할 것도 적고 라이브러리를 쓰는 것이 아니라서 성능면에서도 훨씬 빠를 것이다.

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	static int[] q = new int[2000000];	// 명령의 수는 2,000,000을 안넘음 
	
	static int size = 0;	
	static int front = 0;
	static int back = 0;
	
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		

		while(N-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			
			switch(st.nextToken()){
			case "push": push(Integer.parseInt(st.nextToken())); break;
			case "pop" : pop(); break;
			case "size" : size(); break;
			case "empty" : empty(); break;
			case "front" : front(); break;
			case "back" : back(); break;
			
			}
		}
		System.out.println(sb);
	}
	
	static void push(int n) {
		q[back] = n;
		back++;
		size++;
	}
	
	static void pop() {
		if(size == 0) {
			sb.append(-1).append('\n');
		}
		else {
			sb.append(q[front]).append('\n');	// 맨 앞의 원소를 출력 
			size--;
			front++;	// front가 가리키는 위치 1 증가 
		}
	}
	
	static void size() {
		sb.append(size).append('\n');
	}
	
	static void empty() {
		if(size == 0) {
			sb.append(1).append('\n');
		}
		else sb.append(0).append('\n');
	}
	
	static void front() {
		if(size == 0) { 
			sb.append(-1).append('\n');
		}
		else {
			sb.append(q[front]).append('\n');	 // 맨 앞의 원소 출력 
		}
	}
	
	static void back() {
		if(size == 0) {
			sb.append(-1).append('\n');
		}
		else {
			sb.append(q[back - 1]).append('\n');	// 맨 뒤의 원소 출력 
		}
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 각 필요 기능별로 메소드를 구현해놓았으니 참고하시길 바란다.

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 20597227  -  방법 3 : 직접 구현 방식

채점 번호 : 20597227  -  방법 2 : ArrayDeque 방식

채점 번호 : 20597227  -  방법 1 : LinkedLIst 방식

 

 

 

음.. ArrayDeque와 LinkedList 사이에 큰 차이까지는 있는지는 모르겠다. 몇 번 테스트 해보면 오락가락 하는 것 같은데..

일단 문제 풀이에 가장 최적화 된 방식인 직접 구현방식이 빠르다는 것은 확실한 것 같다.

 

---

• 정리

 

이 번 큐 카테고리를 잘 파악해두는 것이 좋다. 나중에 BFS 탐색 알고리즘에 주로 이용 되는 자료구조라 만약 알고리즘으로 큐를 접했다면 큐에 대한 자료구조 내용을 파악하는 것을 추천드린다.

 

또한 비슷한 문제로 큐 1 문제도 있으니 한 번 풀어보시는 것을 추천한다!