프로그래머스 42587번 프린터

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42587

풀이

큐의 특성을 활용하는 기본적인 문제..인데, 구현하는 데서 삽질을 너무 많이 한 문제입니다..

input이 원래 순서이고, output이 그 프로세스가 처리되는 순서이므로, 원래 순서는 저장되어 있어야 합니다.

그러므로 원래 순서(index), 우선순위(priority)를 함께 담는 Pair class를 구현하여 사용했습니다.

시간 복잡도는 뒤에 높은 우선순위가 있는지 판단하는 계산 때문에, O(n^2) 입니다.

HashMap을 사용했으면, 더 효율적으로 풀 수 있었겠지만, 문제에서 제시한 최대 길이가 100이어서, 그냥 풀었습니다. 실전에서는 이런 거 고민할 시간도 아깝다고 생각됩니다.

풀이

1. while문에서 0번 인덱스(현재 처리해야하는 프로세스) 뒤에 우선순위 높은 게 있는지 확인합니다.

2-1. 우선순위 높은 게 뒤에 있으면, 거기 앞까지 잘라서 queue의 뒤에 붙입니다.

2-2. 우선순위 높은 게 뒤에 없으면, 해당 프로세스를 queue에서 제거합니다.

import java.util.*;

class Solution {
    class Pair {
        int index;
        int priority;
        Pair() {
            index = 0;
            priority = 0;
        }
        Pair(int index, int priority) {
            this.index = index;
            this.priority = priority;
        }
        public void print() {
            System.out.print("(" + this.index + ", " + priority + ")");
        }
    }
    public ArrayList<Pair> cutAndAttach(ArrayList<Pair> list, int startIndex, int endIndex) {
        ArrayList<Pair> temp = new ArrayList<Pair>();
        if(endIndex >= list.size()) endIndex = list.size()-1;
        if(startIndex < 0) startIndex = 0;
        for(int i = startIndex; i <= endIndex; ++i) {
            temp.add(list.get(i));
        }
        for(int i = 0; i < temp.size(); ++i) {
            list.add(temp.get(i));
            list.remove(0);
        }
        return list;
    }
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        ArrayList<Pair> printList = new ArrayList<Pair>();
        for(int i = 0; i < priorities.length; ++i) {
            Pair temp = new Pair(i, priorities[i]);
            printList.add(temp);
        }
        /*
        for(int i = 0; i < printList.size(); ++i) {
            if(i != 0) System.out.print(", ");
            printList.get(i).print();
        }
        System.out.println();
        printList = cutAndAttach(printList, 0, 2);
        for(int i = 0; i < printList.size(); ++i) {
            if(i != 0) System.out.print(", ");
            printList.get(i).print();
        }
        */
        
        int printCount = 0;
        while(printCount < priorities.length && printList.size() > 0) {
            int higherPriorityIndex = 0;
            boolean isHigherExists = false;
            
            for(int i = 1; i < printList.size(); ++i) {
                if(printList.get(0).priority < printList.get(i).priority) {
                    isHigherExists = true;
                    higherPriorityIndex = i;
                    break;
                }
            }
            //현재 차례의 뒤에 높은 우선순위가 있으면 잘라서 뒤로 붙이기
            if(isHigherExists) {
                printList = cutAndAttach(printList, 0, higherPriorityIndex-1);
            } else {//높은 우선순위가 없으면 졸업시키기
                printCount++;
                if(printList.get(0).index == location) {
                    answer = printCount;
                    break;
                }
                printList.remove(0);
            }
        }
        
        return answer;
    }
}