[프로그래머스 / Level2] 프린터 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/42587?language=java 

코딩테스트 연습 - 프린터

 

풀이

인쇄는 무조건 priorities 배열에서 우선순위가 가장 큰 문서(=요소)부터 인쇄된다.
즉, 인쇄의 시작을 끊는 첫번째 문서는 priorities 배열을 내림차순 정렬했을 때 첫번째 요소이다.

1. Integer 타입 요소를 갖는 PriorityQueue(우선순위 큐)를 생성한 뒤, 생성자에 내림차순 Comparator인 Collections.reverseOrder()를 전달해줘서 숫자가 클수록 높은 우선순위를 매기는 PriorityQueue로 만들어준다.
*문제에서 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다고 했기 때문

PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

 

PriorityQueue (우선순위 큐)

Queue인터페이스의 구현체 중 하나로, 저장 순서와 상관없이 우선순위(priority)가 높은 것부터 꺼내진다.

• add() 로 넣은 순서 : 5, 7, 3, 1, 9
• poll() 로 꺼내진 순서 : 1, 3, 5, 7, 9

public static void main(String[] args) {
    int[] arr = { 5, 7, 3, 1, 9 };

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int i : arr) {
        queue.add(i);
    }

    System.out.println(queue);

    while (!queue.isEmpty()) {
        System.out.println(queue.poll());
    }
}

[1, 3, 5, 7, 9]
1
3
5
7
9

 

PriorityQueue 우선순위 변경하기

PriorityQueue는 기본적으로 숫자가 작은 요소일수록 높은 우선순위를 매기며(=숫자가 작을수록 먼저 출력됨), 생성자에 각 요소의 우선순위를 비교할 기준인 Comparator를 매개변수로 전달하면 우선순위 판단 기준을 변경할 수 있다.

 

예를 들어 PriorityQueue의 구성요소가 Integer타입일 때, 우선 순위를 내림차순으로 매기고 싶으면(=숫자가 클수록 먼저 출력됨) PriorityQueue 생성자에 Collections.reverseOrder() Comparator를 매개변수로 전달해주면 된다.

• add() 로 넣은 순서 : 1, 3, 5, 7, 9
• poll() 로 꺼내진 순서 : 9, 7, 5, 3, 1

public static void main(String[] args) {
    int[] arr = { 1, 3, 5, 7, 9 };

    PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
    for (int i : arr) {
        queue.add(i);				// 우선순위 큐 요소 넣기
    }

    System.out.println(queue);			// 우선순위 큐 그대로 출력 (A)
    
    while (!queue.isEmpty()) {
        System.out.println(queue.poll());	// 우선순위 큐 요소 꺼내서 출력 (B)
    }
}

[9, 7, 3, 1, 5]
9
7
5
3
1

 

PriorityQueue는 '우선순위가 높은 것부터 꺼낸다'는 특성에 주의하자. 우선순위가 높은 것 순으로 정렬하여 보관한다는 뜻이 아니기 때문에 PriorityQueue를 그대로 출력했을 때(A)와 실제로 요소를 하나씩 꺼내 출력했을 때(B) 표시되는 순서에 차이가 있을 수 있다.

 

2. add() 또는 offer() 메서드로 priorities 배열의 요소를 PriorityQueue에 하나씩 추가한다.

for (int priority : priorities) {
    queue.offer(priority);
}

 

3. PriorityQueue에서 우선순위가 가장 높은 요소를 하나 읽어온다.

4. 꺼낸 요소의 값(=해당 문서의 우선순위)과 같은 값을 priorities배열에서 찾는다.

5. priorities배열에서 해당 값의 index를 알아야 하기 때문에 for문으로 첫번째 요소(i=0)부터 마지막 요소(i=priorities.length-1)까지 모든 요소를 순회하는데, 이 중에서 PritorityQueue에서 읽은 값과 일치하는 값을 찾을 때만 answer값을 증가하고, 읽어들인 요소를 Queue에서 완전히 꺼내 제거한다.

6. 3~5까지의 과정을 PriorityQueue가 텅 빌때까지 반복하는데, PrioritiyQueue에서 읽어온 값과 priorities배열에서 찾은 값이 일치하면서 현재 탐색중인 위치(i)가 location일 경우 지금까지 증가한 answer값을 반환한다.

while (!queue.isEmpty()) {
    for (int i = 0; i < priorities.length; i++) {
        // 기존 배열에서 우선순위의 값 찾기
        if (queue.peek() == priorities[i]) {
            if (i == location) {
                return answer;
            }
            answer++;
            queue.poll();       // 값을 찾았을 때만 큐에서 빼야함
        }
    }
}

 

[실행 예시]

4개 문서의 우선순위가 차례대로 [2, 1, 3, 2] 일 때, 3번째 문서(priorities[2])는 몇 번째로 출력되는가? = 1번째

priorities	location	return
[2, 1, 3, 2]	2	1

1. PriorityQueue에서 첫번째 요소 3을 꺼낸다.
2. priorities 배열의 각 요소와 비교해본 결과, 3은 priorities[2] 값과 일치한다.
3. 3은 문서 대기목록에서(priorities배열)에서 2번째 문서이다.
   = 문서 대기목록에서 2번째 문서는 첫번째로 출력된다.
4. 사용자가 순번을 알고자하는 문서가 2번째 문서이다.
5. 해당 문서가 사용자가 알고자하는 문서이므로 순번(1)을 그대로 리턴한다.

 

코드

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

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 1;	// 출력순서. 몇 번째로 출력되는가?

        // 우선순위 큐에 문서 우선순위 저장 (우선순위 내림차순 정렬)
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        for (int priority : priorities) {
            queue.offer(priority);
        }

        // 우선순위 높은 순으로 기존 배열에서 일치하는 문서 찾기
        while (!queue.isEmpty()) {
            for (int i = 0; i < priorities.length; i++) {
                if (queue.peek() == priorities[i]) {
                    // PriorityQueue에서 읽은 요소가 location에 위치한 요소일 경우 출력순서 리턴
                    if (i == location) {
                        return answer;
                    }
                    answer++;
                    queue.poll();       // 값을 찾았을 때만 큐에서 빼야함
                }
            }
        }

        return answer;
    }
}

멤버

• int[] priorities : 현재 대기목록에 있는 문서의 중요도 배열 (=문서 개수, 각 문서의 우선순위 값, 문서 순서 정보를 얻을 수 있다.)
• int location : 출력 순서를 알고 싶은 문서의 대기목록 위치
• int answer : location 위치에 있는 문서의 출력 순서
• PriorityQueue<Integer> queue : 문서 중요도 내림차순 우선 순위 큐

처리 로직

• 중요도가 높은 문서 순으로, 해당 문서가 기존 대기 목록에서 어느 위치(몇 번째의)의 문서였는지 체크한다.
  • location 위치의 문서일 경우 => 현재 출력 순번을 리턴
  • location 위치의 문서가 아닐 경우 => 출력 순번 증가, 다음으로 우선순위가 높은 문서 체크하기