[BAEKJOON] 18258 큐 2

문제 요약

• 알고리즘 분류: 큐
• 난이도: Silver4
• 문제내용:
  • 위 명령 조건에 맞게 처리해라~

문제풀이

 이번 문제 큐에 관련된 문제이다. 일반적으로 구현하면 시간 초과가 떠서 큐 이론을 적용한 상태로 풀어야 된다. 

 큐에 대한 자세한 내용은 밑에 사이트에 참조하면된다.

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

Code

Python

 파이썬은 deque라는 라이브러리를 사용하면 된다. popleft사용하면 0번째 인덱스 삭제 걸리는 시간은 O(1)로 나온다. 그리고 deque는 코태에서 많이 사용되서 알아두어야 될 모듈이다.

from collections import deque
import sys
input = sys.stdin.readline
queue = deque()

for _ in range(int(input())):
    commend = input().split()
    if commend[0] == "push":
        queue.append(int(commend[1]))
    elif commend[0] == "pop":
        print(queue.popleft() if queue else - 1)
    elif commend[0] == "size":
        print(len(queue))
    elif commend[0] == "empty":
        print(0 if queue else 1)
    elif commend[0] == "front":
        print(queue[0] if queue else -1)
    elif commend[0] == "back":
        print(queue[-1] if queue else -1)

Java

  자바는 Queue라는 클래스 있는데 사용해보니까 시간 초과가 나온다. 정석대로 구현 하면된다.

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

public class Main {
	
	static int[] queue = new int[2000000];
	static int front = 0;
	static int back = -1;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		String commend;
		Integer value;
		StringBuffer sb = new StringBuffer();
		while(N-- > 0) {
			st = new StringTokenizer(br.readLine());
			commend = st.nextToken();
			switch(commend) {
				case "push":
					push(Integer.parseInt(st.nextToken()));
					break;
				case "pop":
					sb.append(pop()).append("\n");
					break;
				case "size":
					sb.append(size()).append("\n");
					break;
				case "empty":
					sb.append(empty()).append("\n");
					break;
				case "front":
					sb.append(front()).append("\n");
					break;
				case "back":
					sb.append(back()).append("\n");
					break;
			}
			
		}
		System.out.println(sb);	
	}
	
	static void push(int value) {	
		back++;
		queue[back] = value;
	}
	
	static int pop() {
		if(front > back) {
			return -1;
		}
		else {
			int value = queue[front];
			front++;
			return value;
		}
	}
	
	static int size() {
		return back - front + 1;
	}
	
	static int empty() {
		return front > back? 1 : 0;
	}
	
	static int front() {
		return front > back? -1 : queue[front];
	}
	
	static int back() {
		return front > back?  -1 : queue[back]; 
	}
}