/ BOJ

BOJ_10866_덱_JAVA

문제 : 덱

링크 : BOJ_10866_덱

접근 방식

덱의 설명에는 시간복잡도를 O(1)로 하지 않아도 통과는 되지만, 가급적 시간복잡도를 O(1)로 해달라는 요청이 적혀있다.

물론 이전의 큐2 문제를 풀때, 나는 큐를 쓰지 않고 덱을 사용했기 때문에, 시간복잡도가 O(1)인 덱의 코드는 이미 있었다. 해당 코드를 덱 용으로 수정하여 통과했다.

링크 : BOJ_10828_큐2

풀이 방법

  1. push_front : offerFront 메서드를 통해 값을 front에 집어넣는다.

  2. push_back : offerLast 메서드를 통해 값을 Last에 집어넣는다.

  3. pop_front : Integer 변수 k에 pollFront 메서드로 값을 꺼내서 저장한다. Deque 클래스의 poll() 메서드는 queue가 비어있으면 null을 반환하므로, 조건문을 넣어 k가 null일 경우 -1을, null이 아닐경우 k를 출력하게 한다.

  4. pop_back : Integer 변수 k에 pollLast 메서드로 값을 꺼내서 저장한다. Deque 클래스의 poll() 메서드는 queue가 비어있으면 null을 반환하므로, 조건문을 넣어 k가 null일 경우 -1을, null이 아닐경우 k를 출력하게 한다.

  5. size : 현재 deque의 사이즈를 출력한다.

  6. empty : isEmpty 메서드를 통해 deque가 비어있는 지 확인한다. 비어있다면 1을, 비어있지 않다면 0을 출력한다.

  7. front : Integer 변수 k1에 peek 메서드를 통해 가장 첫번쨰 값을 읽어와 저장한다. peek 메서드는 queue가 비어있으면 null을 반환하므로, 조건문을 통해 2번 처럼 구분해준다.

  8. back : Integer 변수 k11에 peekLast 메서드를 통해 queue의 마지막 값을 읽어와 저장한다. peekLast 메서드는 queue가 비어있으면 null을 반환하므로, 조건문을 통해 2번 처럼 구분해준다.

소스 코드


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

import java.util.Deque;
import java.util.LinkedList;


public class BOJ_10866_덱 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Deque<Integer> queue = new LinkedList<Integer>();
		int N = Integer.parseInt(in.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			String[] str = in.readLine().split(" ");
			switch(str[0]) {
			case "push_front":
				queue.offerFirst(Integer.parseInt(str[1]));
				break;
			case "push_back":
				queue.offerLast(Integer.parseInt(str[1]));
				break;
			case "pop_front":
				Integer k = queue.pollFirst();
				if(k == null) {
					sb.append(-1).append('\n');
				}else {
					sb.append(k).append('\n');
				}
				break;
			case "pop_back":
				Integer k2 = queue.pollLast();
				if(k2 == null) {
					sb.append(-1).append('\n');
				}else {
					sb.append(k2).append('\n');
				}
				break;
			case "size":
				// 덱의 사이즈 출력
				sb.append(queue.size()).append('\n');
				break;
			case "empty":
				if(queue.isEmpty()) {
					sb.append(1).append('\n');
				}else{
					sb.append(0).append('\n');
				}
				break;
			case "front":
				Integer k1 = queue.peekFirst();
				if(k1 == null) {
					sb.append(-1).append('\n');
				}else{
					sb.append(k1).append('\n');
				}
				break;
			case "back":
				Integer k11 = queue.peekLast();
				if(k11 == null) {
					sb.append(-1).append('\n');
				}else{
					sb.append(k11).append('\n');
				}
				break;
			}
		}
		System.out.print(sb);
	}

}