lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이번 문제는 문제에서도 나와있듯이 Deque(덱)을 이용해서 큐의 양쪽에서 삽입/삭제를 진행할 수 있기에 쉽게 풀 수 있다.


아이디어 도출

N개의 명령어를 입력받으며 다음을 수행한다.

  • push_X [N] 명령어를 받으면 N을 큐에 삽입한다.
    • push_front 명령어라면 N을 큐의 맨 앞에 삽입한다.
    • push_back 명령어라면 N을 큐의 맨 뒤에 삽입한다.
  • pop_X 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 큐에서 값을 추출하고 출력한다.
    • pop_front 명령어라면 큐의 맨 앞(front) 값을 추출한다.
    • pop_back 명령어라면 큐의 맨 뒤(back) 값을 추출한다.
  • size 명령어를 받으면 현재 큐의 삽입된 값의 개수를 출력한다.
  • empty 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “1”, 비어있지 않다면 “0”을 출력한다.
  • front 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 getFirst() 메서드를 이용해 현재 큐의 front(맨 앞) 값을 출력한다.
  • back 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 getLast() 메서드를 이용해 back(맨 뒤) 값을 출력**한다.


큐의 맨 앞과 맨 뒤 값에 접근해서 삽입/삭제 작업을 추가로 해줘야 한다.
이 작업을 코드로 작성해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// push_X
if(cmd.contains("push")) {
    int num = Integer.parseInt(cmd.split(" ")[1]);
    if(cmd.contains("front")) deq.addFirst(num);
    else deq.addLast(num);
}
// pop_X
else if(cmd.contains("pop")) {
    if(cmd.contains("front")) {
        if(deq.isEmpty()) bw.write("-1"+"\n");
        else bw.write(deq.pollFirst()+"\n");
    }
    else {
        if(deq.isEmpty()) bw.write("-1"+"\n");
        else bw.write(deq.pollLast()+"\n");
    }
}

위 코드대로 push_front일 때는 큐의 맨 앞에 num 값을 삽입하고, push_back일 때는 큐의 맨 뒤에 num 값을 삽입한다.
또한, pop 명령어일 경우 큐가 비어있는지 확인하여 pop_front일 때는 큐의 맨 앞값을 추출하고, pop_back이라면 큐의 맨 뒤값을 추출하면 된다.

나머지 코드는 큐, 큐2 문제에서 작성한 코드와 동일하며, 전체코드는 아래에서 확인할 수 있다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for(int i=0; i<N; i++) {
            String cmd = br.readLine();
            if(cmd.contains("push")) {
                int num = Integer.parseInt(cmd.split(" ")[1]);
                if(cmd.contains("front")) deq.addFirst(num);
                else deq.addLast(num);
            }
            else if(cmd.contains("pop")) {
                if(cmd.contains("front")) {
                    if(deq.isEmpty()) bw.write("-1"+"\n");
                    else bw.write(deq.pollFirst()+"\n");
                }
                else {
                    if(deq.isEmpty()) bw.write("-1"+"\n");
                    else bw.write(deq.pollLast()+"\n");
                }
            }
            else {
                switch(cmd) {
                    case "pop":
                        if(deq.isEmpty()) bw.write("-1"+"\n");
                        else {
                            bw.write(deq.poll()+"\n");
                        }
                        break;
                    case "size":
                        bw.write(deq.size()+"\n");
                        break;
                    case "empty":
                        if(deq.isEmpty()) bw.write("1"+"\n");
                        else bw.write("0"+"\n");
                        break;
                    case "front":
                        if(deq.isEmpty()) bw.write("-1"+"\n");
                        else bw.write(deq.getFirst()+"\n");
                        break;
                    case "back":
                        if(deq.isEmpty()) bw.write("-1"+"\n");
                        else bw.write(deq.getLast()+"\n");
                        break;
                    default:
                        break;
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

  • 최근 큐의 맨 앞과 맨 뒤에 접근하여 삽입/삭제 작업을 진행할 수 있는 Deque(덱)을 활용하는 문제들을 여럿 풀어보고 있다. 단지 개념정도를 알고 푸는 문제들뿐 아니라 난이도가 있는 문제들도 풀어봐야겠다.
  • Queue를 구현하는 또 다른 방식인 LinkedList 라이브러리도 공부해야겠다.

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy