프린터 (Java)

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

 

프로그래머스 코딩테스트 고득점 Kit 프린터 문제 풀이이다.

 

간단하게 리스트만 이용하여 location의 인덱스를 바꾸어줄 생각으로 풀어봤는데 이미 인쇄되는 값까지 저장하고 계산하는 방법이 어려웠고 중요도 배열만큼 반복하면 안 되는 것을 깨닫고 다른 방법을 생각해봤다.

 

손으로 직접 값 변경 단계를 적어보다가 초기 배열 순서와 최종 배열 순서를 비교해서 풀 수 있겠다는 생각까지는 했는데 최종 배열 순서가 간단한 정렬이 아닌 값이 같은 경우 처리도 필요해서 다른 분들의 풀이를 일부 참조했다.

 

우선순위 큐를 써보지 않아서 몰랐는데 우선순위 큐를 이용하면 아주 간단하게 풀 수 있는 문제였다.

우선순위 큐를 이용하여 최종 배열 순서를 구하고 첫 번째 요소와 기존 배열 순서를 비교하여 먼저 인쇄되는 문서 개수를 더해주는 방식으로 접근하면 된다.

 

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        // 큰 숫자가 우선순위가 되도록 우선순위 큐 생성
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        // 우선순위 큐에 중요도가 담긴 배열 순서로 넣으면 자동으로 정렬이 됨
        // ex) [2, 1, 3, 2] -> [3, 2, 2, 1]
        for (int data : priorities) {
            queue.add(data);
        }
        
        int answer = 1;
        while (!queue.isEmpty()) {
            // 우선순위 큐의 첫 번째 요소랑 기존 중요도 목록 배열과 비교
            for (int i = 0; i < priorities.length; i++) {
                if (priorities[i] == queue.peek()) {
                    // 구해야 하는 값이면 더해진 순서 리턴
                    if (i == location) {
                        return answer;
                    }
                    // 구해야 하는 값이 아니라면 
                    answer++;       // 먼저 인쇄되는 문서 더하기
                    queue.poll();   // 큐에서 빼기
                }
            }
        }
        return answer;
    }
}