[프로그래머스,Level 2] 프린터(JAVA 구현)

- 첫 풀이

  문제를 읽는 순간 우선순위 큐가 생각나기는 했지만, 사용해본 적이 없어서 관련된 내용을 간단하게 찾아보았다. 처음 생각으로는 문서의 위치로 주어지는 location으로 인해 우선순위 큐에 우선순위, 인덱스를 필드로 가지는 클래스를 삽입하여 Comparable 인터페이스를 이용하는 방법을 생각해 보았는데, 생각대로 정렬이 되지 않아 다른 방법을 찾아보았다.

 

- 정답풀이

  다른 분들의 풀이를 참고하여 이 문제는 우선순위 큐를 별도의 정렬을 할 필요가 없이 내림차순 정렬한 뒤, priorities 배열을 탐색하며 큐에서 나오는 값과 location이 일치하는 경우를 찾으면 되었다. 

 

  예제 2번을 기준으로 생각해보자.

  1. priorities = 1, 1, 9, 1, 1, 1 6개의 대기목록이 존재한다.

  2. 이를 우선순위 큐에 집어넣으며, 큰 수가 높은 우선순위를 가지게 한다. (9, 1, 1, 1, 1, 1)

  3. 큐를 탐색한다 => 큐에서 나오는 우선순위가 priorities에 저장된 우선순위와 같은 지 찾는다. 

                        => 0번의 1 != 9 이므로 넘어가, 2번 인덱스의 9와 만나면 poll() 후 출력 순서 증가.

  4. ( 1, 1, 1, 1, 1) 다음 1은 2번 인덱스인 9 다음인 3번 인덱스의 1과 비교, 값은 같지만 location과 인덱스가 일치하지 않으므로 poll() 후 출력 순서 증가.

  5. 위와 같은 방식을 진행하면 다시 priorities 배열의 0번 인덱스부터 탐색 값이 같고 location == 인덱스가 일치하므로 출력순서를 반환한다.

 

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
   
    public int solution(int[] priorities, int location) {
        int answer = 0;
        // 1. 큰 수가 우선순위를 갖는 우선순위 큐.
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        // 2. priorities값을 우선순위 큐에 담는다.
        for(int n : priorities){
            pq.offer(n);
        }
        
        // 3. 큐가 빌 때 까지 반복 == 모든 대기목록이 비워질 때 까지.
        while(!pq.isEmpty()){
            // 4. 큐에서 나오는 값과 매칭되는 경우를 탐색.
            for(int i = 0;i<priorities.length;i++){
                // 5. 값만 일치하는 경우 해당 문서 출력.
                if(pq.peek() == priorities[i] ){
                    pq.poll();
                    answer++;
                    // 6. 값과 위치가 모두 일치하면 answer을 반환.
                    if(location == i ) return answer;
                }
            }
            
        }
                
        return answer;
    }
}