[Java] 백준(실버-4) 15828번 - Router

자세한 테스트케이스 데이터는 문제링크를 참고하자.

문제 풀이

---

이번 문제는 큐의 개념을 잘 알고 있다면 쉽게 풀 수 있는 문제이다.

아이디어 도출

• 양수가 주어졌을 때 큐의 크기가 버퍼 크기(N)보다 작다면 양수를 큐에 삽입한다.
• 0이 주어졌을 때 큐에서 값을 추출(삭제)한다.
• -1이 주어졌을 때 큐를 확인하여 큐가 비어있다면 “empty”를, 비어있지 않다면 큐의 원소를 출력한다.

테스트케이스를 잘 보면 큐의 선입선출 성질을 그대로 적용하였음을 알 수 있다.
에제 1을 한번 살펴보자.

N(버퍼의 크기) = 5, Q(큐).size = 0
1 => N > Q.size => 큐에 1 삽입 Q[1]
2 => N > Q.size => 큐에 2 삽입 Q[1, 2]
0 => 큐에서 1 추출 => Q[2]
3 => N > Q.size => 큐에 3 삽입 Q[2, 3]
4 => N > Q.size => 큐에 4 삽입 Q[2, 3, 4]
0 => 큐에서 2 추출 => Q[3, 4]
5 => N > Q.size => 큐에 5 삽입 Q[3, 4, 5]
6 => N > Q.size => 큐에 6 삽입 Q[3, 4, 5, 6]
0 => 큐에서 3 추출 => [4, 5, 6]
0 => 큐에서 6 추출 => [5, 6]
-1 => Q[5, 6] 출력

위와 같은 방식대로 요구사항에 대한 솔루션을 도출할 수 있다. 바로 코드를 작성해보자.

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

버퍼의 크기 N을 입력받고 연산간에 활용할 Queue를 하나 생성하자.

 while(true) {
    int info = Integer.parseInt(br.readLine());
    if(info > 0) {
        if(qu.size() < N) qu.offer(info);
    }
    else if(info == 0) qu.poll(); 
    else break;
}
if(qu.isEmpty()) bw.write("empty"+"\n");
for(int num : qu) bw.write(num+"\n");

핵심 로직에 대한 내용은 다음과 같다.

1. -1을 입력받을 때까지 while문으로 입력을 받는다.
2. 0보다 큰 양수를 입력받으면 N보다 큐의 크기가 작은지 확인하고 큐에 양수를 삽입한다.
3. 0을 입력받으면 현재 큐에서 원소 하나를 추출(삭제)한다.
4. -1을 입력받는다면 while문을 탈출한 후 큐가 비어있는지 확인하여 비어있다면 “empty”를, 비어있지 않다면 큐의 원소를 출력하면 된다.

작성코드

---

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<>();

        while(true) {
            int info = Integer.parseInt(br.readLine());
            if(info > 0) {
                if(qu.size() < N) qu.offer(info);
            }
            else if(info == 0) qu.poll(); 
            else break;
        }
        if(qu.isEmpty()) bw.write("empty"+"\n");
        for(int num : qu) bw.write(num+"\n");

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

회고

• 큐의 개념을 잘 숙지하고 있다면 쉽게 풀 수 있었던 문제였다. 큐를 응용하는 문제들도 많이 풀어봐야겠다.

출처

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