[프로그래머스] 프린터

문제 링크

1. 문제 해결

필자는 아래 두개의 자료구조를 이용하여 문제를 해결하였다

1. TreeMap
2. Queue

1-1. 전처리

문서의 정보를 담는 클래스를 선언한다. 클래스 내에 있는 변수는 아래와 같은 의미다.

1. 현재 문서의 우선 순위
2. 현재 문서의 번호

TreeMap은 Map의 일종으로 키 값을 오름차순으로 정렬시킨다.
문제에서는 우선순위가 높은 문서부터 프린트 가 되므로 TreeMap의 키 값을 내림차순으로 정렬시켜야 하기에 객체 생성시, Collections.reverseOrder()를 매개변수로 넣는다.

1-2. 알고리즘

전처리 과정을 통해 만들어진 Map을 이용하여 우선순위가 높은 순으로 큐에 있는 문서들을 빼는데
아래와 같은 분기점을 신경써야한다.

• 현재 문서의 우선순위와 현재 Map의 우선순위 비교
  • 같은 경우, 뽑는 순서를 증가시키고 현재 Map의 우선 순위(key)에 해당되는 값을 감소시킨다.
  • 다른 경우, 현재 문서를 큐에 다시 넣는다.

2. 소스 코드

import java.util.*;
class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Paper> q = new LinkedList<>();
        Map<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());
        
        for(int i =0 ; i < priorities.length ; i++){
            q.add(new Paper(priorities[i],i));
            if(map.containsKey(priorities[i]))
                map.replace(priorities[i], map.get(priorities[i])+1);
            else
                map.put(priorities[i],1);
        }
        
        int order =0 ;
        outter : for(int rank : map.keySet()){
            int count = map.get(rank);
            
            while(count > 0){
                Paper cur_p = q.poll();
                
                if(cur_p.prior != rank)
                    q.add(cur_p);
                else{
                    count--;
                    order++; //순서 증가
                    
                    if(cur_p.num == location)
                        break outter;
                }
            }
        }
        
        return order;
    }
    
    private class Paper{
        int prior, num;
        
        public Paper(int p , int n){
            this.prior = p;
            this.num = n;
        }
    }
}