[BOJ] 10845 - 큐 (Java)

알고리즘

• 자료 구조
• 큐

1. 문제

2. Idea

• switch-case문을 통한 명령어 처리
• Deque 사용

  Deque 메소드

  • deque.append(x) : x를 데크의 오른쪽 끝에 삽입한다
  • deque.appendleft(x) : x를 데크의 왼쪽 끝에 삽입한다
  • deque.pop() : 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다
  • deque.popleft() : 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다
  • deque.extend(array) : 배열 array를 순환하면서 데크의 오른쪽에 추가한다
  • deque.extendleft(array) : 배열 array를 순환하면서 데크의 왼쪽에 추가한다
  • deque.remove(x) : x를 데크에서 찾아 삭제한다
  • deque.rotate(num) : 데크를 num만큼 회전한다 (양수면 오른쪽, 음수는 왼쪽으로)

  Deque를 쓰는 이유

• deque는 list보다 속도가 빠르고, 쓰레드 환경에서 안전하다.
• pop(0)와 같은 메서드를 수행할 때 리스트의 경우 O(N)연산을 수행하지만 deque는 O(1) 연산을 수행한다.
• 따라서, push와 pop이 빈번한 알고리즘의 경우, list보다 deque를 사용하는것이 효율적이며 속도가 더 빠르다.

3. 풀이

3.1. 변수 선언 및 초기화

• int N: 명령어 수
• Deque dq
  • double-ended-queue의 줄임말
  • 양방향에서 데이터를 처리할 수 있는 queue형 자료구조
  • stack + queue

        int N=Integer.parseInt(br.readLine());
        Deque<Integer> dq=new ArrayDeque<>();

3.2. 명령어 처리 및 결과 출력

• 명령어에 따른 큐 처리
• 결과 출력

			switch (st.nextToken()){
                case "push": //값 추가
                    dq.addLast(Integer.valueOf(st.nextToken())); break;
                case "pop": //맨 앞 값 삭제 및 출력
                    if(!dq.isEmpty()){
                        System.out.println(dq.peekFirst());
                        dq.removeFirst();}
                    else {System.out.println(-1);} break;
                case "size": //크기 조회
                    System.out.println(dq.size()); break;
                case "empty": //비어있는가?
                    if(!dq.isEmpty()){System.out.println(0);}
                    else{System.out.println(1);} break;
                case "front": //맨 앞 조회
                    if(!dq.isEmpty()){System.out.println(dq.peekFirst());}
                    else {System.out.println(-1);} break;
                case "back": //맨 뒤 조회
                    if(!dq.isEmpty()){System.out.println(dq.peekLast());}
                    else {System.out.println(-1);} break;
            }

4. 전체코드

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        Deque<Integer> dq=new ArrayDeque<>();
        for(int i=0; i<N; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            switch (st.nextToken()){
                case "push": //값 추가
                    dq.addLast(Integer.valueOf(st.nextToken())); break;
                case "pop": //맨 앞 값 삭제 및 출력
                    if(!dq.isEmpty()){
                        System.out.println(dq.peekFirst());
                        dq.removeFirst();}
                    else {System.out.println(-1);} break;
                case "size": //크기 조회
                    System.out.println(dq.size()); break;
                case "empty": //비어있는가?
                    if(!dq.isEmpty()){System.out.println(0);}
                    else{System.out.println(1);} break;
                case "front": //맨 앞 조회
                    if(!dq.isEmpty()){System.out.println(dq.peekFirst());}
                    else {System.out.println(-1);} break;
                case "back": //맨 뒤 조회
                    if(!dq.isEmpty()){System.out.println(dq.peekLast());}
                    else {System.out.println(-1);} break;
            }
        }
    }
}