lango

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

3 minute read




문제 풀이

이제 큐,덱 카테고리 문제를 풀기 시작했다. 스택과 더불어 큐 문제 풀 때는 구현과정이 직관적(?)으로 느껴져 재밌게 풀고 있는 것 같다.
이번 문제는 시간 제한이 1초로 빡센 편이니 Scanner보다는 BufferedReader 및 BufferedWriter를 활용하는게 시간 단축에 조금이나마 도움이 되지 않을까 생각한다.

일단 큐(Queue)에 대한 원리를 어느 정도 알고 있어야 한다.
잠깐 큐에 대해서 설명하자면 큐(Queue) 자료구조는 선입선출(FIFO) 구조로 먼저 들어간 데이터가 먼저 나오는 형식으로 이루어진다.

또한, Java에서는 Queue 인터페이스를 선언하여 사용할 경우 맨 앞 값을 가져올 수는 있지만(peek() 메서드) 맨 뒤 값을 가져올 수 있는 back()과 같은 메서드가 없기 때문에 맨 뒤 값을 꺼내올 수 없어 직접 구해야 한다.

이를 해결하기 위해서는 Deque 인터페이스, 흔히 말하는 ‘덱’을 활용하거나 LinkedList 라이브러리를 활용하여 풀 수 있다.
하지만 위 두가지 방식이 아닌 Queue 인터페이스를 사용하는데 직접 back을 구하는 방식으로 풀어보았다.


아이디어 도출

  • push [N]이라면 N을 큐에 삽입한다. 이 때 back(맨 뒤값)에 N의 값을 저장한다.
  • pop이라면 큐에서 값을 추출한다. 추출된 front(맨 앞값)를 출력한다.
  • size라면 현재 큐의 삽입된 값의 개수를 출력한다.
  • empty라면 큐가 비어있는지 확인후 비어있다면 1, 비어있지 않다면 0을 출력한다.
  • front라면 맨 앞값을 출력해야 하기에 qu.peek() 메서드를 통해 큐의 front(맨 앞값)를 출력한다.
  • back이라면 push일 때 담아둔 back 값을 출력한다.


back을 N으로 지정한 이유는 큐의 FIFO 구조를 이용하기 위함이다. 1,2,3을 순서대로 큐에 삽입하는 예를 들어보자.

1
2
3
4
5
6

push 1
    queue => front [1] back
push 2
    queue => front [1,2] back
push 3
    queue => front [1,2,3] back

순서대로 1,2,3을 큐에 삽입하면서 front(맨 앞값)는 제일 먼저 삽입한 값이고, back(맨 뒤값)은 제일 최신에 삽입한 값이 된다.
그래서 큐에 N을 삽입할 때마다 N을 back에 담아둔다면 맨 뒤값을 기록하고 있게 되는 것이다.


이제 코드를 작성해보자.

1
2
3

int N = Integer.parseInt(br.readLine());
Queue<Integer> qu = new LinkedList<>();
int back = -1;

먼저 명령의 갯수 N을 입력받고, push [N] 명령어를 받을 때마다 N을 담을 Queue, 맨 뒤값을 저장해둘 back 변수를 선언하자.

back을 -1로 초기화한 이유는?
혹여 push 명령어가 없어 back 값이 변경되지 않았을 경우 큐가 비어있기에 back 명령어가 들어왔을 때 “-1”을 출력해야 하기 때문이다.

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

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

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

  • push [N] 명령어를 받으면 N을 큐에 삽입하고 back에 N 값을 저장한다.
  • pop 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 front(맨 앞값)를 추출하고 출력한다.
  • size 명령어를 받으면 현재 큐의 삽입된 값의 개수를 출력한다.
  • empty 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “1”, 비어있지 않다면 “0”을 출력한다.
  • front 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 현재 큐의 front(맨 앞값)를 출력한다.
  • back 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 push 명령 조건에서 저장해둔 back의 값을 출력한다.



작성코드

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

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());
        Queue<Integer> qu = new LinkedList<>();
        int back = -1;

        for(int i=0; i<N; i++) {
            String cmd = br.readLine();
            if(cmd.contains("push")) {
                int num = Integer.parseInt(cmd.split(" ")[1]);
                qu.offer(num);
                back = num;
            }
            else {
                switch(cmd) {
                    case "pop":
                        if(qu.isEmpty()) bw.write("-1"+"\n");
                        else bw.write(qu.poll()+"\n");
                        break;
                    case "size":
                        bw.write(qu.size()+"\n");
                        break;
                    case "empty":
                        if(qu.isEmpty()) bw.write("1"+"\n");
                        else bw.write("0"+"\n");
                        break;
                    case "front":
                        if(qu.isEmpty()) bw.write("-1"+"\n");
                        else bw.write(qu.peek()+"\n");
                        break;
                    case "back":
                        if(qu.isEmpty()) bw.write("-1"+"\n");
                        else bw.write(back+"\n");
                        break;
                    default:
                        break;
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

  • 스택에 이어 큐를 활용하는 문제를 푸는데 스택 문제를 풀 때와 비슷하게 재미를 느끼는 것 같다. LIFO, FIFO 같은 직관적인 속성들이 문제 접근에 도움을 주는 것 같다.
  • 나중에 맨 뒤값을 제공해주는 Deque, LinkedList를 활용하는 방식도 꼭 풀어봐야겠다.

출처

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

You may also enjoy