Lv.2 : 프로세스

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 큐에서 앞 원소를 꺼낸다. (poll)
• 꺼낸 원소보다 우선순위가 더 높은 원소가 있다면, 꺼낸 원소를 다시 큐에 넣는다. (add)
• 우선순위대로 원소를 꺼내다가 처음 위치가 location인 원소가 나올 때의 꺼낸 원소 수를 반환한다.

🔸 문제 풀이 🔸

• 원소들의 우선순위와 처음 위치를 기억하기위해 두 요소를 담은 클래스 Process를 만들어 Queue에 저장한다.
• 우선순위대로 꺼내기 위해 PriorityQueue에 원소를 저장한다.
• 우선순위 큐에 나온 원소와 같은 원소가 나올 때 까지 일반 큐에서 원소를 꺼낸다.
• 꺼낸 원소의 처음 위치가 location과 같다면 현재까지 우선순위 큐에서 꺼낸 원소들의 수를 반환한다.

---

🔸 코드 🔸

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.ArrayDeque;
import java.util.Collections;

class Solution {
    private class Process {
        private int priority;
        private int seq;

        public Process(int priority, int seq) {
            this.priority = priority;
            this.seq = seq;
        }
    }

    public int solution(int[] priorities, int location) {
        Queue<Process> que = new ArrayDeque<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < priorities.length; i++) {
            pq.add(priorities[i]);
            que.add(new Process(priorities[i], i));
        }

        for (int i = 1; i <= priorities.length; i++) {

            int target = pq.poll();

            Process process = que.poll();
            while(process.priority != target) {
                que.add(process);
                process = que.poll();
            }

            if (process.seq == location)
                return i;
        }

        return -1;
    }
}

 

🔸 코드 해석 🔸

• 우선순위와 초기 위치를 저장하기 위해 Process 클래스를 만들어 사용했다.
• 우선순위를 담은 int형 배열 priorites를 일반 큐와 우선순위 큐에 각각 복사해 저장한다.
• 우선순위 큐에서 나온 원소가 일반 큐에서 나올 때 까지 문제의 계산을 반복한다.
• 꺼낸 원소의 초기 위치가 location과 같다면 현재 우선 순위 큐에서 꺼낸 원소의 수를 반환한다.

---

🔸 end 🔸

• 첫 풀이에서는 우선순위 큐만 두고, Process 클래스에 Comparable을 넣어 사용했다.
  • 예제는 통과했지만, 문제의 1번과 2번 조건에서 꺼낸 원소를 다시 넣는 작업이 없어서 실행 실패했다.
  • 아마 예제는 우선순위 큐로 돌려서도 되도록 함정을 파놓은 것 같다.
• 다른 코드를 보니 우선순위 큐 대신 일반 정렬을 사용하거나, 일반 큐도 사용하지 않고 location 값을 옮겨가며 인덱스 움직임으로 큐를 대신하는 방식의 풀이가 있었다.
  • 정렬도 1번 일어나기 때문에 일반 정렬도 효율이 비슷할 것 같고, 큐 대신 location을 움직이는건 초기 위치를 기억하지 않아도 되서 메모리와 효율 모두 챙길 수 있는 좋은 솔루션 같다.