[백준알고리즘-JAVA]18258번 풀이(큐2) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 18258번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 18258 (큐 2)

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

 

명령은 총 여섯 가지이다.

 

push X: 정수 X를 큐에 넣는 연산이다.

pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

size: 큐에 들어있는 정수의 개수를 출력한다.

empty: 큐가 비어있으면 1, 아니면 0을 출력한다.

front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

입력 예제

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

출력 예제

1
2
2
0
1
2
-1
0
1
-1
0
3

실패 코드

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

public class Main {

	static int N;
	static ArrayList<Integer> q = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		
		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			String str = st.nextToken();
			
			if(st.hasMoreTokens())
				push(Integer.parseInt(st.nextToken()));
			else if(str.equals("pop")) {
				sb.append(pop()).append("\n");
			}else if(str.equals("size")) {
				sb.append(size()).append("\n");
			}else if(str.equals("empty")) {
				sb.append(empty()).append("\n");
			}else if(str.equals("front")) {
				sb.append(front()).append("\n");
			}else if(str.equals("back")) {
				sb.append(back()).append("\n");
			}
			
		}
		
		System.out.println(sb);

		}
	
	public static void push(int i) {
		q.add(i);
	}
	public static int pop() {
		if(q.isEmpty()) 
			return -1;
		int temp = q.get(0);
		
		q.remove(0);
		return temp;
		
	}
	public static int size() {
		if(q.isEmpty()) 
			return 0;
		
		return q.size();
	}
	public static int empty() {
		if(q.isEmpty()) 
			return 1;
		
		return 0;
	}
	public static int front() {
		return q.get(0);
	}
	public static int back() {
		if(q.isEmpty()) 
			return -1;
		
		return q.get(q.size()-1);
	}
	
}

실패한 코드이기 하지만, 실패한 사유는 바로 시간 초과.... 바로 ArrayList로 구현했기 때문입니다. 입력에 따른 출력은 잘 나오지만 말입니다. 아래 step을 따라가 보면서 arraylist와 linkedlist의 차이에 대해서 알아봅시다.

성공 코드

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

public class Main {

	static int N;
	static Deque<Integer> q = new LinkedList<>();
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		
		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			String str = st.nextToken();
			
			if(st.hasMoreTokens())
				push(Integer.parseInt(st.nextToken()));
			else if(str.equals("pop")) {
				sb.append(pop()).append("\n");
			}else if(str.equals("size")) {
				sb.append(size()).append("\n");
			}else if(str.equals("empty")) {
				sb.append(empty()).append("\n");
			}else if(str.equals("front")) {
				sb.append(front()).append("\n");
			}else if(str.equals("back")) {
				sb.append(back()).append("\n");
			}
		}
		
		System.out.println(sb);

		}
	
	public static void push(int i) {
		q.add(i);
	}
	public static int pop() {
		if(q.isEmpty()) 
			return -1;

		return q.pop();
	}
	public static int size() {
		if(q.isEmpty()) 
			return 0;
		
		return q.size();
	}
	public static int empty() {
		if(q.isEmpty()) 
			return 1;
		
		return 0;
	}
	public static int front() {
		if(q.isEmpty()) 
			return -1;
		
		return q.getFirst();
	}
	public static int back() {
		if(q.isEmpty()) 
			return -1;
		
		return q.getLast();
	}
	
}

코드가 상당히 길어 보이지만, 상당히 쉽게 구현할 수 있는 코드입니다. 입력이 주어진 대로 바로 해결해 주시면 되거든요. 여기서 핵심은 바로 큐를 어떠한 방식으로 구현할 것인가입니다.

 

step을 따라가 보죠

---

알고리즘 흐름도

 입력받기 -> 주어진 큐의 동작 구현하기 -> 입력에 따라 출력하기

---

STEP1 큐를 구현하는 방법

 

 현재 자바에서 큐를 구현하는 여러 방법이 있습니다. 큐를 컬렉션을 사용하여 ArrayList, LinkedList을 활용한 방법 배열을 활용하는 방법 대표적으로 이 3가지가 있습니다.

(더 있을 수 있지만 아직 필자는 알지 못합니다.)

 

ArrayList의 경우 아래처럼 사용합니다.

Queue<Integer> queue = new ArrayList<>();

이런 식으로 큐를 구현하죠

 

LinkedList의 경우 아래처럼 구현이 됩니다,

Queue<Integer> queue = new LinkedList<>();

 

배열의 경우는 배열 자체를 큐라 생각하고 인덱스를 통해서 FIFO를 구현하게 됩니다.

(배열의 경우 길이가 길어지기에 생략합니다.)

 

-> 본글에서는 DEQUE를 사용한 이유는.... 딱히 큰 이유가 있지 않습니다... ㅎㅎ 그냥 사용하다 보니 이게 편하게 되어 사용하게 되었습니다.

 

(여기서 DEQUE란 큐와는 다르게 먼저 들어온 입력이 먼저 출력이 될 수도 있으며 마지막에 들어온 입력이 출력될 수 도 있는 양쪽으로 입출력이 가능한 큐이다.)

 

이러한 큐들은 각자 나름의 장단점이 있다. 보통 대게 큐를 구현할 때는 컬렉션을 많이 이용하기에 이에 따라서 컬렉션의 시간 복잡도에서 생각해볼 수 있다.

시간 복잡도를 일일이 설명하기에는 설명의 한계가 있기에 아래 표를 참고하면 된다.

 

 

여기를 참고하면 어느 한순간 때 각 컬렉션을 써야 할지 감이 오실 겁니다.

뭐 대체로 LinkedList를 사용하고 특별히 값이나 인덱스를 통 해거 탐색을 원한다면 ArrayList를 사용해야 한다.

---

STEP2 각 메서드 구현

 뭐.... 사실 각 메서드를 구현하는 것은 아주 쉽습니다...

public static void push(int i) {
		q.add(i);
	}
	public static int pop() {
		if(q.isEmpty()) 
			return -1;

		return q.pop();
	}
	public static int size() {
		if(q.isEmpty()) 
			return 0;
		
		return q.size();
	}
	public static int empty() {
		if(q.isEmpty()) 
			return 1;
		
		return 0;
	}
	public static int front() {
		if(q.isEmpty()) 
			return -1;
		
		return q.getFirst();
	}
	public static int back() {
		if(q.isEmpty()) 
			return -1;
		
		return q.getLast();
	}

여기서 문제에서 주어진 예외상황들 q가 비어있을 경우만 고려해서 해당 값을 반환해 주면 끝... 사실 설명할 것도 없습니다

---

STEP 3 PUSH를 위한 입력값 판별하기

 다른 입력값과는 다르게 push는 입력할 값도 추가됩니다.

 

이를 걸러주기 위해 저는 StringTokenizer를 사용했습니다.

		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			String str = st.nextToken();
			
			if(st.hasMoreTokens())
				push(Integer.parseInt(st.nextToken()));
			else if(str.equals("pop")) {
				sb.append(pop()).append("\n");
			}else if(str.equals("size")) {
				sb.append(size()).append("\n");
			}else if(str.equals("empty")) {
				sb.append(empty()).append("\n");
			}else if(str.equals("front")) {
				sb.append(front()).append("\n");
			}else if(str.equals("back")) {
				sb.append(back()).append("\n");
			}

입력이 되었으면 일단 str에서 nexttoken을 먼저 한번 실행해줍니다. 그 후 아직도 stringtokenizer에 토큰이 남아있다면, 그게 바로 push가 되겠죠. 이러한 방법을 통해서 해결해 주었습니다. 뭐 split과 같은 다른 방법으로도 가능하답니다.