[PG] 프린터 JAVA

programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

출력할 인쇄물의 우선순위를 담은 배열 int[] priorities, 타겟 인쇄물의 인덱스를 담은 int location 이 주어진다.

각 인쇄물의 우선순위를 반영하여 차례대로 출력할 때 타겟 인쇄물이 몇번째로 인쇄되는지를 반환해야한다.

 

1. 최초 대기열 순서는 priorities의 순서와 같다.

2. 맨 앞의 인쇄물을 꺼내서 뒤의 인쇄물들과 우선순위를 비교한다. 

3. 뒤의 인쇄물들 중 나보다 우선순위가 높은 것이 하나라도 있다면 맨 앞의 인쇄물을 맨 뒤로 보낸다.

4. 모든 인쇄물이 나보다 우선순위가 낮다면 그것을 출력한다.

 

 

풀이 .

import java.util.*;

class Work {
    int loc;  // 최초 대기열의 index
    int priority;  // 우선순위
    int done;  // 작업 완료되는 순서
    public Work(int loc, int priority) {
        this.loc = loc;
        this.priority = priority;
    }
}

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        List<Work> list = new LinkedList<Work>();

        Work target = null;
        for(int i = 0; i < priorities.length; i++) {
            list.add(new Work(i, priorities[i]));
            if(i == location) {  // 마지막에 정답 추출하기 위한 타겟 객체 참조
                target = list.get(i);
            }
        }

        int cnt = 1;
        while(!list.isEmpty()) {
            int p = list.get(0).priority;
            for(int i = 0; i < list.size(); i++) {
                if(p < list.get(i).priority) {  // 나보다 우선인 놈 있으면 맨 뒤로 넘긴다
                    list.add(list.remove(0));
                    break;
                }
                if(i == list.size() - 1) {  // 마지막 원소까지 검사 완료했으면
                    list.get(0).done = cnt++;  // 완료 순서 저장하고
                    list.remove(0);  // 대기열에서 제거
                }
            }
        }
        answer = target.done;
        return answer;
    }
}

인쇄물들을 관리하기 위해 Work 클래스를 만들었다.

작업이 완료된 객체들은 따로 저장하지 않고 바로 제거해버리기 때문에 Work target을 사용해 타겟 객체를 따로 참조했다.

나머지는 문제의 조건을 그대로 따라했다.

 

시간복잡도가 조금 걸리는데.. 

 

일단 priorities의 길이의 상한은 100

 

1개의 원소를 제거 가능한지 불가능한지 확인하는 데 n만큼이 걸린다.

우선순위가 가장 높은 원소가 맨 뒤에 있다고 가정하면 1개의 원소를 제거하는 데 n^2이 걸린다.

이런식으로 n개의 원소를 제거하려면 결국 O(n^3)이 걸린다.

 

100^3 = 1,000,000 이라 시간초과가 나진 않았지만 굉장히 비효율적...