[프로그래머스] 프린터

프로그래머스 <프린터>

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

프로그래머스

---

프린터

아래와 같은 방식으로 인쇄 작업을 수행하는 프린터에서 내가 요청한 문서가 몇 번째로 인쇄되는지 구하여라.

1. 인쇄 대기목록의 가장 앞에 있는 문서(D)를 대기목록에서 꺼낸다.
2. 나머지 인쇄 대기목록에서  D보다 중요도가 높은 문서가 한 개라도 존재하면 D를 대기목록의 가장 마지막에 넣는다.
3. 그렇지 않으면 D를 인쇄한다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서의 위치 location이 들어온다.

 

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 반환한다.

---

문제해결

주어진 수행 방식을 그대로 구현하면 된다.

 

먼저 큐에 인쇄 대기목록을 모두 넣었다. 원래 몇 번째 문서였는지 기억하기 위해 Tuple이라는 클래스를 따로 만들어서 사용하였다. 큐에 넣는 과정에서 가장 높은 우선순위가 무엇인지 구해 max에 저장하였고 각 우선순위에 맞는 문서가 몇 개인지 count 배열에 저장하였다.

 

• 큐에서 값을 하나씩 꺼내면서 max값과 같다면 문서를 인쇄한다.
  • 인쇄한 문서가 내가 요청한 문서라면 몇 번째 인쇄되었는지를 의미하는 order 값을 반환하면 된다.
  • 그렇지 않은 경우에는 count 배열의 값을 update 하고, 필요하다면 max 값도 update 한다.
• 그렇지 않은 경우에는 꺼낸 값을 다시 큐에 넣는다.

---

코드

import java.util.*;
class Solution {
    static class Tuple{
        int idx, priority;
        public Tuple(int idx, int priority){
            this.idx = idx;
            this.priority = priority;
        }
    }
    public int solution(int[] priorities, int location) {

        Queue<Tuple> Q = new ArrayDeque<>();
        int[] count = new int[10];  // count[i] : 우선순위가 i인 작업의 개수
        int max = Integer.MIN_VALUE;    // max : 현재 가장 높은 우선순위
        for(int i = 0; i < priorities.length; i++){
            count[priorities[i]]++;
            Q.add(new Tuple(i, priorities[i]));
            max = Math.max(max, priorities[i]);
        }
        int order = 0;  // order : 몇 번째로 인쇄된 문서인지
        while(!Q.isEmpty()){
            Tuple tp = Q.poll();
            if(tp.priority == max){ // 현재 문서가 가장 우선순위가 높은 문서라면
                order++;
                if(tp.idx == location){ // 현재 문서가 내가 인쇄를 요청한 문서라면
                    break;
                }
                count[max]--;
                if(count[max] == 0){
                    while(true){
                        max--;
                        if(count[max] != 0){
                            break;
                        }
                    }
                }
            }else{
                Q.add(tp);
            }
        }
        return order;
    }
}

시도해본 테스트케이스

/*
[4, 3, 2, 1]
2

3
---------------
[1, 2, 3, 4]
2

2
---------------
[2, 2, 2, 2, 2, 2]
3

4
---------------
*/

---

결과

---