프린터

Posted on Edited on In , ,

문제정의

각 인쇄할 용지의 우선순위가 주어진다. 용지는 앞에서부터 인쇄하되, 만약 인쇄대기목록에 우선순위가 높은 것이 있다면 맨 뒤로 보내진다. 내가 인쇄를 처음에 요청한 문서의 인덱스가 주어질 때 언제 그 문서가 인쇄될 지 계산하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;

public class Printer {
    
    //프로그래머스 문제풀이 level2 프린터

    public static void main(String[] args)
    {
        int[] priorities = {1, 1, 9, 1, 1, 1};
        int location = 0;
        int answer = 0;
        ArrayList<Integer> papers = new ArrayList<>();
        int order = 1;
        boolean isFirst;
        for(int i = 0; i < priorities.length; i++)
            papers.add(i);
        while(papers.size() != 0)
        {
            isFirst = true;
            int idx = papers.get(0);
            
            for(int i = 1; i < papers.size(); i++)
            {
                if(priorities[papers.get(i)] > priorities[idx])
                {
                    papers.remove(0);
                    papers.add(idx);
                    isFirst = false;
                    break;
                }
            }
            if(isFirst)
            {
                if(idx == location)
                {
                    answer = order;
                    break;
                }
                else
                {
                    papers.remove(0);
                }
                order++;
            }
                
        }
        System.out.print(answer);
    }
    
}
필자는 어레이리스트로 문제를 풀었다. 시간을 줄이고 싶었지만, 잘 모르겠어서 문제가 시키는 그대로 했다. papers에 각 문서의 위치를 담고, 맨 앞부터 차례대로 보는 것이다. 22-31번째 줄을 보면, 우선순위를 탐색하는 코드가 있다. 만약 현재 맨 앞에 있는 것보다 우선순위가 큰 문서가 있으면, 현재 문서를 맨 뒤로 보내고, 대기문서의 첫번째에 있지 않기 때문에 isFisrt를 false로 한다. 만약에 인쇄될 문서보다 우선순위가 높은 것이 없으면 isFirst는 true가 될 것이다. 이때 이 문서가 내가 인쇄요청한 문서라면, 답을 반환하고 그렇지 않다면 order를 증가하고 해당 문서를 제거(출력)한다.

이 문제의 시간복잡도는 내가 인쇄 요청한 문서가 오름차순 우선순위의 가장 마지막 문서일 경우이다. 이 경우 문서의 개수를 n이라 하면, O(n2)이다.

테스트



다른 사람의 풀이를 보니 answer를 앞에서부터 볼 인덱스로 하고 l을 내가 요청한 문서가 현재 위치한 곳을 나타내는 것으로 하여 일일이 priority를 다 비교하지 않아도 문제를 풀었다. 정말 대단하다고 생각한다. 나도 멋진 아이디어가 생각날 때까지 갈고 닦아야겠다.