프로그래머스 프린터(priorities) 정답 코드

난이도 ★★★☆☆

 

문제를 보시려면 여기를 클릭

 

 

 

힌트

문제에서 설명하는 그대로, 사람이 생각하는 그대로를 코딩으로 옮겼습니다. (Stack 을 쓰지 않음) 다만 자료구조를 TreeMap, LinkedList 로 써서 성능을 많이 향상시켰습니다.

 

 

 

이하는 코드입니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
 
public class Solution {
    public int solution(int[] priorities, int location) {
        TreeMap<Integer, Integer> countMap = new TreeMap<>(); // 뒤에 나보다 큰 녀석이 있는지 확인용
        LinkedList<Doc> remains = new LinkedList<>();
 
        for (int i = 0; i < priorities.length; i++) {
            int priority = priorities[i];
            Integer count = countMap.get(priority);
 
            if (count == null) {
                countMap.put(priority, 1);
            } else {
                countMap.put(priority, count + 1);
            }
 
            Doc doc = new Doc();
            doc.id = i;
            doc.priority = priority;
            remains.add(doc);
        }
 
        List<Doc> results = new ArrayList<>(); // 최종 결과
 
        while (!remains.isEmpty()) {
            Doc doc = remains.getFirst();
 
            Integer higherPriority = countMap.higherKey(doc.priority); // TreeMap을 쓴 이유임
 
            if (higherPriority == null) { // 나보다 큰 녀석이 뒤에 없음
                results.add(doc);
                remains.removeFirst();
 
                int count = countMap.get(doc.priority);
 
                if (count > 1) {
                    countMap.put(doc.priority, count - 1);
                } else {
                    countMap.remove(doc.priority);
                }
            } else {
                // 맨앞의 녀석을 맨뒤로 보냄. LinkedList를 쓴 이유임
                remains.removeFirst();
                remains.addLast(doc);
            }
        }
 
        int answer = 0;
 
        for (int i = 0; i < results.size(); i++) {
            Doc doc = results.get(i);
 
            if (doc.id == location) {
                answer = i + 1;
                break;
            }
        }
 
        return answer;
    }
 
    private class Doc {
        int id;
        int priority;
    }
}