프로그래머스 레벨2 - 프린터 with Java

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.
예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

 

입출력 예

priorities location return
[2, 1, 3, 2] 2 1
[1, 1, 9, 1, 1, 1] 0 5

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.
예제 #2
6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

 

나의 코드 1

//// 나의 첫 번째 풀이 ////
public class Programmers_Printer {
    public int solution (int[] priorities, int location) {
    	// 인자로 받은 priorities를 queue형태로 변환해 저장할 변수
    	LinkedList<Integer> waitingLine = new LinkedList<>();
        // 프린트된 작업들을 정렬해줄 queue 변수
        LinkedList<Integer> printed = new LinkedList<>();

		// 인자로 받은 priorities를 queue 형태로 변환
        for (int priority : priorities) {
            waitingLine.add(priority);
        }
		
        // 결국 priorities의 모든 작업이 printed로 넘어가야 하므로 
        while (printed.size() < priorities.length){
            System.out.println(waitingLine);
            // 최댓값 리뉴얼 해주기 //
            int max = waitingLine.get(0);
            for(int i = 0; i < waitingLine.size(); i++){
                if(max < waitingLine.get(i)) {
                    max = waitingLine.get(i);
                }
            }
            // 가장 앞 인덱스에 있는(가장 먼저 할당된) 원소가 최댓값보다 작을시
            if (waitingLine.peek() < max){
            	// 가장 앞 인덱스 원소를 빼서 제거하고 맨 뒤에 넣는다.
                waitingLine.offer(waitingLine.poll());
            } else { // 최댓값보다 크다면 printed 리스트로 옮겨준다.
            	printed.add(waitingLine.poll());
            }
        }
        return printed;
}

우선 나는 자바를 배운적도 얼마 안되서스택과 큐도 전혀 몰랐는데, 코딩테스트를 풀다보니 이걸 활용한 문제들이 꽤 있는걸 보았고, 이 문제를 처음 봤을때 이건 큐를 써야할 것 같다 싶어 개념을 찾아보고 사용법을 알아봤다.

 

poll이니 add니 하는것도 처음 써보고 이래 저래 시행착오를 거치며 위의 코드까지는 완성했다. 결과물도, 큐에서 가장 앞 원소인 peek를 큐 내의 최대값과 비교해서 작으면 뒤로 넘기고, 최대값이라면 제거하고 printed에 추가하는것까지 완성했다. 결과창의 앞 7줄이 waitingList이고 그 다음줄이 printed이다. printed를 보면 3, 2, 1, 1로, 우선순위에 맞게 잘 정렬된것을 볼 수 있다.

 

그런데 문제는 location을 어떻게 할 것인가였다. 인덱스로 추적을 하자니 각 원소별로 고유값이 있어야 할 것 같은데, 원소끼리 중복(1이 두개인것처럼)되기도 하고 인덱스가 계속 변하기때문에 어찌 추적을 할 것인가 계속 고민했다. 그러다가 어찌 저찌 하여 cnt 변수로 printed가 채워지는 횟수를 카운트해서 location에 해당하는 원소의 프린트 순서를 맞게 뽑아냈으나, 프로그래머스에서 몇몇 테스트케이스에서만 통과하는걸 보고 또 좌절했다.

 

큐 자체를 처음 접하는거라 확실치도 않고 해서 결국 다른 사람의 코드를 참고하게 되었다. 우선 큐를 사용한다는 접근성은 맞았다!! 하지만 저번 코테문제에서도 발견했던 나의 문제가 또 드러났다. 굳이 안해도 될 과정들을 다 해버리면서 문제를 복잡하게 끌고간다는 것.... 굳이 printed를 또 만들어서 정렬할 필요가 없는게, 사실 저 printed는 waitingList를 내림차순 정렬한거나 똑같기 때문... 어차피 answer값을 printed에서 뽑아낼수도 없는 노릇이고, 아무리생각해봐도 순회하다가 최댓값을 만났을 때 그 원소를 poll하는 횟수를 가지고 지지고 볶아야 할텐데 굳이 저걸 왜 구해놨을까...

 

나는 문제를 읽으면서 백지에 정리를 하면서 푸는 스타일인데 문제의 문장 그대로 변수를 세우고 과정도 문장 설명 고대로 따라가려다보니 그런 것 같다. 다른 사람들의 코드를 보니 역시 answer를 return할수만 있을 정도의 간단명료한 코드를 짰다.

 

우선, 그러기 위해선 priority queue를 알아야 했다.

 

제너릭으로 큐를 생성하는 방법은 내가 참고한 블로스 포스팅엔 연결리스트밖에 없어서 그것만 있는줄 알았다... 알고보니 priority que라는 '우선순위 큐'라는 방법도 있었다. 우선순위 큐는 밑의 블로그를 참고했다.

http://asuraiv.blogspot.com/2015/11/java-priorityqueue.html

[JAVA] 우선순위(PriorityQueue) 큐

우선순위 큐는 기존의 큐가 배열이나 연결리스트(내가 처음으로 사용한 방법)를 통해서 만들어져서 순서가 중요했다. 큐는 가장 먼저 입력된 데이터를 출력하고 삭제하고 지지고 볶는건데 그렇기 때문에 인덱스가 중요했다. 항상 0번째 인덱스의 원소를 가지고 지지고 볶는다.

 

[처음 배운 개념이라 이부분부터 사실과 다를수 있음] 반면 우선순위 큐는 인덱스와 상관없이 원소값이 가장 작은 순서대로 정렬이 된다. priority queue 클래스 자체가 comparator 인터페이스를 implement 하고 있어서 원소가 오름차순 소팅이 되고, 원소 하나하나가 '우선순위'가 되어 가장 높은 우선순위, 즉 원소의 숫자가 작을수록 앞에 오게 되는 원리다.

 

근데 내가 풀었던 이 프린터 문제는 원소 값이 높은 것이 먼저 출력되야 하기 때문에 역소팅을 해줘야 하는데, 그 방법은 collection 클래스의 reverseorder 메소드를 사용하는 것이었다. 그렇게되면 내가 이전 코드에서 힘겹게 만들었던 printed 큐가 한큐에 해결된다. 그리고 그렇게 내림차순된 큐와 원래의 배열 priorities를 순회하면서 같은지를 보는 것이다. 그리고 location과 해당 순회차의 i가 같은지 확인한다.

 

나의 코드 2

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

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        // 내림차순 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

		// 큐로 변형
        for(int priority : priorities){
            pq.add(priority);
        }
        
        // pq가 모두 poll될동안
        while(!pq.isEmpty()){
        	// 원래 배열 priorities를 순회하면서
            for(int i = 0; i < priorities.length; i++){
            	// pq의 최대값이자 가장 첫 원소가 priorities의 원소와 같을 때
                if(pq.peek() == priorities[i]){
                	// 최대값이므로 프린트를 해준다. 즉, pq에서 제거한다.
                    pq.poll();
                    // 몇개나 프린트됬는지 알아야하기 때문에 증가시켜준다.
                    answer++;
                    // 근데 우리가 알고자하는 원소의 인덱스인 location이 i와 같으면 
                    if (location == i){
                    	// 더이상 반복하며 메모리 소비할 필요 없으므로 clear와 break 해준다.
                        pq.clear();
                        break;
                    }
                }
            }
        }
        return answer;
    }
    
}

priorities의 인덱스는 바뀌지 않는다는것을 생각하지 못한것이 핵심이지 않았나 싶다. 아무리 reverseOrder이니, priorityqueue니를 몰랐어도 어쨌든 내 방식으로 최댓값을 활용했으니 접근법이 틀리진 않았다고 믿는다. 하지만 그래도 자바 자료구조에 대해 더 많이 깊게 알수록 더 효율적인 코드를 짤 수 있다는 건 사실이다.