프로그래머스 lv2 프린터

문제 링크

프린터

풀이

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> idxQ = new LinkedList<>();
        ArrayList<Integer> finalIdxList = new ArrayList<>();

        for (int i = 0; i < priorities.length; i++) {
            queue.add(priorities[i]);
            idxQ.add(i);
        }

        while (!queue.isEmpty()){
            int t = queue.poll();
            boolean isBiggest = true;
            for(int i : queue){
                if(t < i){
                    queue.add(t);
                    idxQ.add(idxQ.poll());
                    isBiggest = false;
                    break;
                }
            }

            if(isBiggest){
                finalIdxList.add(idxQ.poll());
            }
        }

        return finalIdxList.indexOf(location) + 1;
    }
}

소감

• 문제에서 대놓고 큐 문제입니다~라고 알려주길래 쉽겠지 했는데 생각보다 어려웠다.
• 나는 인덱스 전용 큐를 따로 만들어두고, 가장 큰 값이 아닌 경우 큐에 더해질때 해당 인덱스도 같이 더해질 수 있도록 하였다.
• 그리고 만약 가장 큰 값인 경우에는 기존 큐에서 해당 값만 poll하는 것이 아니라 인덱스 큐에서도 같이 poll해서 가장 큰 값 순으로 해당 값의 인덱스를 리스트에 넣을 수 있도록 했다.
• 다른 사람들의 풀이를 보았을 때 이야 이런걸 생각도 하는구나 싶었던 사람의 풀이를 가져왔다.

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int l = location;

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities);
        int size = priorities.length-1;

        while(!que.isEmpty()){
            Integer i = que.poll();
            if (i == priorities[size - answer]){
                answer++;
                l--;
                if (l < 0) break;
            } else {
                que.add(i);
                l--;
                if (l < 0) l = que.size()-1;
            }
        }

        return answer;
    }
}    

• Arrays.sort를 사용하여서 정렬을 하였다..정렬을 하면 location의 위치는 어떻게 찾아내는건가 싶었다.
• 정렬을 하여서 큐를 돌리며 해당 값이 가장 큰 값이랑 같은지 비교한다.
• 아니면 값을 큐에 다시 더하고, 로케이션 값을 뺀다. 만약에 로케이션 값이 0보다 작으면, 다시 큐의 사이즈보다 한개 작게(하나는 뽑아낸거니까) 로케이션 값을 잡는다.
• 이렇게하면 꼭 모든 값을 정렬하지 않고도 중간에 원하는 값을 뽑아낼 수 있다.
• 시간 복잡도가 o(n)이 되었다. 이런 생각은 어떻게 하는걸까..