[자바] 프로그래머스 - 프린터 (programmers java)

문제 : programmers-프린터

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

  문제에서 제시된 대로 시뮬레이션을 돌려주면 된다. 이 때 서브 문제로 문제를 나눠서 생각해보자.

 

1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다.

2. 현재 꺼내지 않은 대기목록에서 중요도가 가장 높은 값을 알 수 있어야 한다.

3. location으로 지정된 문서의 위치를 항상 알 수 있어야 한다.

 

위의 3가지를 모두 할 수 있다면 이 문제를 풀 수 있다. 그럼 각각 어떻게 해야할지 생각해보자.

 

 

1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다.

  사실 이걸 만족하는 자료구조는 엄청 많다. 그 중 앞에서 꺼내고, 뒤에 넣는 행위 각각을 O(1)로 가능한 자료구조만 추려보자면 LinkedList, Queue, Deque 정도가 있다. 이 중 어떤걸 선택해도 상관없다.

 

이하 코드에선 Deque를 선택했다.

 

 

2. 현재 꺼내지 않은 대기목록에서 중요도가 가장 높은 값을 알 수 있어야 한다.

  이것도 다양한 방법이 있다. 대강 생각나는 것들만 적어보면 다음과 같다.

 

A. '1'에서 LinkedList를 선택하고, 매번 전체를 iterator로 순회하면서 최대 중요도값을 찾는다(O(N^2)). 코드는 아래처럼 될 것이다.

private int getMax(LinkedList<Integer> list) {
        Iterator<Integer> it = list.iterator();
        int max = -1;
        while (it.hasNext()) {
            max = Math.max(max, it.next());
        }
        return max;
    }

 

B. max heap(priority queue)에 미리 넣어둬서, 빠질 때 마다 pq에서 poll 해주면 매번 top이 맥스값이다(O(NlogN)). 코드는 아래처럼 될 것이다.

private PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    private int getMax() {
        return pq.peek();
    }
    private void remove() {
        pq.poll();
    }

 

C. 어차피 중요도가 최대 9가지 뿐이므로 각 중요도가 몇 번 나왔는지 카운팅한다. 그리고 어떠한 중요도가 빠질 때 마다 cnt[해당 중요도]--; 를 해준다면 0이 되기 전까지는 해당 중요도가 맥스값이다(O(10N)). 이 때 별도 변수를 하나 더 유지하면서 cnt[해당 중요도]가 0이 될 때만 다시 중요도들을 뒤에서부터 순회하며 맥스값을 찾는다면 그보다 더 줄일 수 있다(최대 10회가량 변경되므로).

 

이하 코드에선 'C'를 선택했다. 코드는 이하 코드에서 확인해보자.

 

 

3. location으로 지정된 문서의 위치를 항상 알 수 있어야 한다.

  이하 location으로 지정된 문서를 A라고 칭하겠다. A가 location 위치에서 시작해서, 앞의 문서를 꺼낼 때 마다 location은 -1이 될 것이다. 그리고 A가 대기목록의 맨 앞에 왔을 때, 맥스 중요도가 아니어서 문서의 맨 뒤로 가게된다면 당연히 A의 위치 location은 '현재 대기목록 길이 -1'이 될 것이다. 그리고 A가 대기목록의 맨 앞인지는 location==0인지로 확인하면 된다.

 

  이렇게 짜기 어렵다면, 클래스로 짜면 된다. 거기에 중요도를 나타내는 int priority와 함께 A인지 여부를 나타내는 boolean값 isTarget(이름은 알아서!)를 두고, 클래스 단위로 '1','2'를 수행하면 A는 항상 자신이 A인지 여부와 함께 옮겨다니므로 별도로 location을 계산하지 않아도 되서 쉽게 짤 수 있다.

 

이하 코드에서는 두가지 경우로 모두 짜봤다. 2번째 코드는 내 생각엔 아마 가장 최적화 시킨거라 저것보다 시간복잡도가 빠르게 짜긴 힘들 것 같다.

 

 

코드(클래스 넣어서 쉽게 한 것) : github

 

코드(클래스 없이 location 직접 조정) : github