[백준 18258] 큐 2(Python, Java)

https://www.acmicpc.net/problem/18258

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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

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

풀이 설명

1. 문제 제목부터 알 수 있듯이, 큐 자료구조를 사용해야 시간초과 없이 통과할 수 있다.

2. 파이썬에서는 deque 자료구조를 임포트하여 appendleft, pop을 사용했다.

3. 자바에서는 Queue 라이브러리를 사용하려다가, Queue에는 맨 뒤 원소를 확인하는 방법이 없기때문에 Queue의 부모 인터페이스인 LinkedList를 사용했다.

  3-1. LinkedList에는 큐의 맨 뒤 원소를 반환하는 peekLast() 함수가 있다.

4. 또한, 자바 코드에서 연산 하나를 수행할 때마다 system.out으로 출력을 하면 시간초과가 발생한다.

  4-1. 시간초과를 피하려면 StringBuilder를 사용하여 연산을 수행할 때마다 sb.append로 추가만 해주고 마지막에 한번에 출력해야 한다.

Python3 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
q = deque([])

for i in range(n):
    op = input().split()
    if op[0] == "push":
        q.appendleft(int(op[1]))
    elif op[0] == "front":
        if q:
            print(q[-1])
        else:
            print(-1)
    elif op[0] == "back":
        if q:
            print(q[0])
        else:
            print(-1)
    elif op[0] == "size":
        print(len(q))
    elif op[0] == "empty":
        if not q:
            print(1)
        else:
            print(0)
    else:
        if not q:
            print(-1)
        else:
            print(q.pop())

Java 코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		LinkedList<Integer> q = new LinkedList<>();
		int num = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<num; i++) {
			String[] op = br.readLine().split(" ");
			switch(op[0]) {
			case "push":
				q.offer(Integer.parseInt(op[1]));
				break;
			case "pop":
				if(q.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(q.poll()).append("\n");
				break;
			case "front":
				if(q.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(q.peek()).append("\n");
				break;
			case "back":
				if(q.isEmpty())
					sb.append(-1).append("\n");
				else
					sb.append(q.peekLast()).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;
			}
		}
		System.out.println(sb);
	}
}