[백준] 1966번_프린터 큐(Java)

문제 풀이

백준의 1966번 문제입니다. 문제 출처

(1) 문제 파악

FIFO(First-In-First-Out) 방식인 기존의 프린터와는 다르게 문서의 중요도에 따라 프린트하는 순서를 조정하는 프린터 프로그램을 만드는 문제입니다.

(2) 문제 풀이 방법 생각하기

• 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

문서들을 비교하기 위해서는 가장 높은 중요도의 값이 무엇인지만 알면 됩니다. 이를 위해 중요도의 값들을 정렬한 뒤 제일 뒤에 있는 (오름차순으로 정렬했을 때) 값과 비교해서 원하는 값을 찾아나가면 됩니다!

(3) 시간 복잡도 확인

시간 제한은 2초 입니다. 즉, 대략 2억번 연산 안에 문제를 해결해야 합니다.

• List.remove()는 O(n)의 시간 복잡도를 가집니다.
• 전체 배열을 순회하며 중요도를 비교합니다 -> 최악의 경우 O(N)

이기 떄문에 최악의 경우 시간 복잡도는 O(N^2) 입니다. N의 최대값은 100이므로 문제 해결이 가능합니다!

(4) 구현

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        
        int[] arr;
        StringTokenizer st;
        int n, targetIdx;
        for(int i=0; i<testCase; i++) { 
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            targetIdx = Integer.parseInt(st.nextToken());
      
            arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            
            int result = solution(arr, targetIdx);
            System.out.println(result);
        }
        
        br.close();
    }
    
    static int solution(int[] arr, int targetIdx) {
        int count = 0;
        List<Integer> sorted_list = new ArrayList<>(); // 중요도의 값을 정렬할 리스트입니다.
        
        for(int i=0; i<arr.length; i++) {
            sorted_list.add(arr[i]);
        }
        Collections.sort(sorted_list); // 중요도 오름차순 정렬 
        
        int idx = 0; 
        while(sorted_list.size()>0) {
            if(sorted_list.get(sorted_list.size()-1) == arr[idx]) { // 현재 나온 문서가 제일 큰 중요도를 가지고 있다면
                if(idx == targetIdx) break; 
                else { // 인쇄
                    arr[idx] = 0;
                    sorted_list.remove(sorted_list.size()-1);
                    count++;
                }
            } 
            idx++;
            if(idx == arr.length) idx = 0;
        }
        
        return count+1;
    }
}