알고리즘 풀이 - 프로그래머스(프린터, 큐)

 

문제 설명

 

일반적으로 프린터는 인쇄 요청이 들어온 순서 대로 인쇄하지만, 이 프린터는 중요도가 높은 문서를 먼저 인쇄하도록 개발되어 아래와 같은 규칙을 기반으로 수행된다.

 

수행 규칙

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

위 수행 규칙에 따라 프린터가 인쇄할 때, 문서의 중요도가 담긴 배열과 인쇄 요청 문서의 위치를 매개변수로 주어지는 경우 인쇄 요청을 받은 문서가 몇 번째로 인쇄되는지 반환하는 함수를 작성하라.

 

매개 변수

배열 prioritiees : 인쇄 대기목록의 문서의 중요도
변수 location : 인쇄 요청된 문서의 현재 위치

 

예시

아래와 같이 A, B, C, D의 문서의 순서로 대기 목록에 있고, 중요도가 2, 1, 3, 2 라면 어떻게 될까?

1. 문서 A는 우선 순위가 2이고 문서 C가 대기열 중 2보다 높은 우선 순위(3)를 갖고 있어 문서 A는 제일 뒤로 이동
   현재 순서 : B C D A
2. 문서 B는 우선 순위가 1이라서 다른 문서에 비해 우선 순위가 낮아 제일 뒤로 이동
   현재 순서 : C D A B
3. 문서 C는 가장 우선 순위가 높다 ① 번째로 인쇄됨
   현재 순서 : D A B
4. 문서 D는 현재 우선 순위가 가장 높아 ② 번째로 인쇄됨
   현재 순서 : A B
5. 문서 A는 다시 현재 우선 순위가 가장 높다 ③ 번째로 인쇄됨
   현재 순서 : B
6. 문서 B는 다시 현재 우선 순위가 가장 높아 ④ 번째로 인쇄됨

즉, C - D - A - B 의 순서로 인쇄된다.

 

해결 방법1 - Queue를 이용해 해결

 

Paper 즉, 대기 순서에 있는 문서들의 현재 대기 위치와 우선 순위를 저장하는 Class를 정의한다. 각 문서를 Queue에 저장해두고 빼면서 현재 대기 순서(배열)의 문서의 우선 순위와 비교하여 순위가 더 낮으면 Queue의 가장 뒤에 문서를 저장한다. 아니라면 문서를 인쇄하며, 이 과정이 Queue가 빌 때까지 반복한다.

public int solution(int[] priorities, int location){
        int answer = 0;
        Queue<Paper> q1 = new LinkedList<>();
        for(int i=0; i < priorities.length; i++){
            Paper p = new Paper(i, priorities[i]);
            q1.offer(p);
        }

        while(!q1.isEmpty()){
            Paper current = q1.poll();
            boolean flag = false;
            for(int i=0; i < q1.size(); i++){
                if(((LinkedList<Paper>) q1).get(i).priority > current.priority){
                    q1.offer(current);
                    flag = true;
                    break;
                }
            }
            if(flag) continue;
            answer++;
            if(current.index == location){
                break;
            }
        }
        return answer;
    }
    private class Paper{
        int index;
        int priority;
        public Paper(int index, int priority){
            this.index = index;
            this.priority = priority;
        }
    }

 

테스트 결과는 아래와 같다.