문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.
   예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

분석

룰은 다음과 같다.

1. 리스트의 첫 요소가 리스트의 최댓값이면 remove한다.
2. 리스트의 첫 요소가 리스트의 최댓값이 아니면 리스트의 마지막으로 이동시킨다.

포인트는, 리스트의 변화에 따라 리스트의 최솟값이 변할 수 있다는 것이다.
어떻게 하면 리스트의 첫 요소와 리스트의 최솟값을 비교할 수 있을까?

매 번 리스트의 최솟값을 탐색하면 되겠지만 시간이 오래 걸릴 것이다.

생각한 방법은, 원래의 리스트를 내림차순으로 정렬한 역순 리스트를 만들고 원본 리스트과 역순 리스트의 첫 요소들끼리 비교하는 것이다.

풀이

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[] priorities, int location) {
        LinkedList<Integer> list = Arrays.stream(priorities).boxed().collect(Collectors.toCollection(LinkedList::new));
        LinkedList<Integer> sorted = list.stream()
            .sorted(Comparator.reverseOrder())
            .collect(Collectors.toCollection(LinkedList::new));

        int count = 0;
        int idx = location;
        while(true) {
            if(list.get(0) >= sorted.get(0)) {
                count++;
                if(idx == 0) return count;
                list.removeFirst();
                sorted.removeFirst();
            } else {
                list.addLast(list.removeFirst());
            }
            idx = decIdx(idx, list.size());
        }
    }
    
    private int decIdx(int n, int size) {
        return n - 1 < 0 ? size - 1 : n - 1;
    }
    
}

성능 올리기

역순 리스트를 정렬된 배열로 변경

• 배열을 정렬하고 배열의 인덱스를 하나씩 증가시키는 것으로 대체할 수 있을 것이다.
• 스트림 비용이 사라진다.
• 리스트 요소 제거 비용을 없앨 수 있을 것이다.

스트림을 쓰지 않고 리스트 생성

• 스트림 비용이 사라진다.

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[] priorities, int location) {
        LinkedList<Integer> list = new LinkedList<>();
        for(int p : priorities) list.add(p);
        
        Arrays.sort(priorities);
        int count = 0;
        int idx = location;
        while(true) {
            int p = list.removeFirst();
            // ↓ 우변의 값은 항상 최댓값을 의미하므로 좌변(p)가 더 클 순 없다.
            if(p == priorities[priorities.length - 1 - count]) { 
                count++;
                if(idx == 0) // 최댓값이고 목표 인덱스인 경우
                    return count;
                // 우선순위가 같지만 목표 인덱스(location)가 아닌 경우
                idx--; // idx!=0이므로 idx--해서 음수가 될 순 없다.
            } else {
                list.addLast(p);
                idx = idx - 1 < 0 ? list.size() - 1 : idx - 1;
            }
        }
    }
}

대부분 스트림 비용 차이인 듯 보인다.

마무리

스트림만으로 시간 차이가 나는 것은 데이터가 작기 때문이다.
데이터가 커질수록 스트림 비용의 비중은 작아질 것이다.

첫 풀이를 하고 다른 사람의 답안을 보았는데 내 답안과 퍽 비슷했다.
성능 올리기를 하고 나니 거의 똑같아졌다.