[Java] 백준(실버-3) 1966번 - 프린터 큐

문제 풀이

---

이 문제는 큐(Queue) 자료구조를 잘 숙지하고 있다면 조금만 응용해서 풀 수 있다.

아이디어 도출

문제를 풀기 위해 생각해낸 아이디어는 다음과 같다.

1. 주어지는 입력값인 N을 토대로, 0부터 N-1까지 큐에 삽입한다. 그러면 M번째 문서와 비교하기 수월하다.
2. int 배열을 만들어 0번째 자리에는 문서, 1번째 자리에는 해당 문서의 중요도를 저장한 후 이 배열을 큐에 삽입한다.
3. 큐를 순회하면서 큐의 첫번째 원소를 꺼낸 후 나머지 원소들과 비교하여 중요도가 가장 큰 원소인지 비교한다.
4. 만약 꺼낸 현재 원소보다 중요도가 큰 다른 원소가 있다면, 꺼낸 원소들을 순서대로 큐에 마지막에 삽입한다.
5. 만약 꺼낸 현재 원소가 찾고 있던 M번째 문서이면서, 가장 큰 중요도를 가진 원소라면, 순회를 종료한다.
6. 순회 종료 후 큐에서 원소를 꺼낼 때마다 카운트하여 저장했던 변수값을 출력한다.

이때, 중첩으로 반복문을 사용하기 때문에 내부 반복문에서 중요도를 판별하는 것과 외부 반복문에서 중요도를 판별하는 것을 잘 고려해야 한다.

마지막으로, 큐에서 가장 중요도가 큰 원소가 꺼내질 때마다 카운트를 1씩 세다가 M번째 원소가 꺼내졌다면 순회를 종료하면 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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 T = Integer.parseInt(br.readLine());
        for(int idx=0; idx<T; idx++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            // ** get() 메소드 사용을 위핸 Queue 인터페이스가 아닌 LinkedList를 사용했다.
            LinkedList<int[]> q = new LinkedList<>();
            st = new StringTokenizer(br.readLine());            
            for(int num=0; num<N; num++) {
                q.add(new int[]{num, Integer.parseInt(st.nextToken())});
            }

            int cnt = 0;
            while(!q.isEmpty()) {
                
                // 큐에서 꺼낸 첫번째 원소
                int[] first = q.poll();
                
                // 꺼낸 원소가 가장 큰 중요도를 가지는지 판단할 boolean 변수
                boolean isMax = true;
                
                // 꺼낸 첫번째 원소와 나머지 원소들을 순회하며 비교
                for(int i=0; i<q.size(); i++) {
                    // 꺼낸 원소의 중요도가 나머지 원소의 중요도보다 작을 경우
                    // 꺼냈던 첫 현재 원소와 나머지 원소를 큐의 마지막에 삽입한다.
                    if(first[1] < q.get(i)[1]) {
                        q.offer(first);
                        for(int j=0; j<i; j++) {
                            q.offer(q.poll());
                        }
                        // 꺼낸 현재 원소가 가장 큰 중요도를 가지고 있지 않기에
                        // isMax를 false로 하고 순회 종료
                        isMax = false;
                        break;
                    }
                }
                // 중요도가 큰 원소를 큐에서 꺼낼 때마다 cnt 변수에 카운트 1씩 증가
                // 이때, 꺼낸 첫번째 원소의 중요도가 가장 높았다면 while문 종료
                if(isMax == true) {
                    cnt++;
                    if(first[0] == M) {
                        break;
                    }
                }
            }
            bw.write(cnt+"\n");
        }
        bw.close();
        br.close();
    }
}

출처

---

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