[프로그래머스] 프린터 (level 2) java

문제 

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

코딩테스트 연습 - 프린터 | 프로그래머스

 

이 문제를 풀기에 앞서 priorityQueue<>(Collections.reversOrder()); 값이 내가 예상한 대로 나오지 않아 그 부분에 대해 따로 정리해 두었다.

[자료구조] 우선순위 큐(PriorityQueue) + 힙(Heap) - 2

 

소스코드

public int solution(int[] priorities, int location) {
        int answer = 1;

        PriorityQueue priority = new PriorityQueue<>(Collections.reverseOrder());

        for(int task : priorities){
            priority.add(task);
            System.out.println(priority);
        }
        //{2,5,4,1,3};

        System.out.println(priority);
        while(!priority.isEmpty()){
            for(int i=0; i<priorities.length; i++){
                if(priorities[i] == (int)priority.peek()) {
                    if(i == location){
                        return answer;
                    }
                    priority.poll();
                    answer++;
                }
            }
        }

        return answer;
    }

여기서 for문 안이 핵심인데, 정리 내용중에도 써놨듯이

삽입의 위치를 찾기 위해 첫 번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

우선순위 큐에서 가장 우선순위가 높은 작업이 해당 배열 priorities[i]의 우선순위와 같은지 비교하고 같으면 우선순위 큐를 poll하고, poll이 된 개수를 카운트한다. 작업 배열 priorities[]의 인덱스를 location변수와 같을 때 카운트된 것 리턴!

 

LinkedList를 사용한 풀이(2019.12.29)

문제를 새로 다시 풀었지만, 같은 부분에서 막히고 똑같은 상황이 되풀이되었다..

알고리즘 푸는 실력은 도대체 늘지않는다.

큐에 넣은 요소의 위치와 location을 도대체 어떻게 맞춰줘야할지 떠오르지가 않았다

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

        Queue<Integer> que = new LinkedList<>();

        for(int pri : priorities){
            que.add(pri);
        }

        Arrays.sort(priorities); //우선순위를 비교하기 위해 오름 차순 정렬
        int length = priorities.length-1; //오름차순 한 마지막 요소가 가장 큰 수 

        while(!que.isEmpty()){
            int current = que.poll();

            //우선순위가 가장 높은 수 == 현재 큐에 담긴 (프린트 순서)가 같으면
            if(current == priorities[length - answer]){
                answer++;
                location--;
                if(location<0){
                    break;
                }
            }else{
                //처음에 que.poll을 했던 수를 add 함으로써 맨 뒤로 밀림
                que.add(current);
                location--; // 1
                if(location<0){
                    location = que.size()-1;
                }
            }
        }
        return answer;
    }

location이 0보다 작다는 소리는 큐의 맨 앞까지 우선순위 검증을 한 상태다.

if 문의 location-- 경우에는 우선순위와 같은 상태이므로 반복을 종료시키면 되지만,

else 문의 location-- 경우에는 우선순위에서 밀려 제일 뒤로 순위가 밀린 상태이므로 제일 마지막 인덱스를 가리키도록 재할당해준다.

배열을 오름차순으로 정렬해놓았으므로, 가장 높은 우선순위를 비교했다면, 더이상 그 수를 바라 볼 필요가 없다. 그 다음으로 큰 우선순위를 바라볼 수 있도록 length - answer 를 수행한다.

어렵다..