[프로그래머스] Level 2 프린터 (JAVA)

문제

---

1차 풀이 (2021.02.16)

1. queue에 document를 생성해서 다 집어 넣는다.
2. queue의 head를 차례대로 탐색하면서 조건을 체크한다.
   • head가 queue 중 최우선순위라면 출력을 한다는 의미에서 answer을 증가시킨다.
   • 만약 방금 프린트 한 head의 index가 location이면 종료조건을 만족시키므로 break한다.
   • 최우선순위가 아니라면 다시 queue에 집어 넣는다.

isPrintable()은 람다와 스트림을 사용해서 구현했다. noneMatch()는 주어진 조건을 만족하는 element가 하나라도 존재하는 지 체크하고 boolean 값을 리턴한다.

코드

import java.util.*;

class Solution {    
    
    private Queue<Document> queue;
    private int answer;

    public int solution(int[] priorities, int location) {
        queue = new LinkedList<>();
        for (int i = 0; i < priorities.length; i++) queue.offer(new Document(priorities[i], i));
        while (!queue.isEmpty()) {
            Document head = queue.poll();
            if (isPrintable(head)) {
                answer++;
                if (head.index == location) break;
            } else queue.offer(head);
        }
        return answer;
    }

    private boolean isPrintable(Document head) {
        return queue.stream().noneMatch(document -> document.priority > head.priority);
    }
}

class Document {
    int priority;
    int index;

    public Document(int priority, int index) {
        this.priority = priority;
        this.index = index;
    }
}

---

2차 풀이 (2021.08.25)

반 년 전 풀이때는 stream을 사용해서 모든 priority를 검사하도록 했었다. 시간복잡도가 쓰레기라는 뜻이다.

그래서 이번엔 priorities를 정렬해서 priorty와 maxPriority를 비교하도록 했다.

코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int targetIndex) {
        Queue<Integer> queue = new LinkedList<>();
        for(int each : priorities){
            queue.add(each);
        }

        Arrays.sort(priorities);
        int size = priorities.length;

        int printedCount = 0;
        while(!queue.isEmpty()){
            int priority = queue.poll();
            int maxPriority = priorities[size - printedCount - 1];
            
            if (priority == maxPriority) {
                printedCount++;
                
                if (targetIndex == 0) {
                    return printedCount;
                } else {
                    targetIndex--;
                }
            } else {
                queue.offer(priority);
                
                if (targetIndex > 0) {
                    targetIndex--;                    
                } else {
                    targetIndex = queue.size()-1;
                }
            }
        }
        return printedCount;
    }
}