[프로그래머스 JAVA] 프로세스

[프로그래머스] 프로세스 : https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

---

문제 조건 정리

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

---

입력 / 출력

 

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고,

우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

 

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와,

몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때,

해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

---

문제를 옳게 풀기 전

 

1. 우선순위큐를 사용할 생각을 못하고 큐를 사용하기로 함.
2. 큐를 사용하려고 하니, 각 프로세스의 priority와 입력순서 idx를 클래스로 정의하기로 함.
3. 가장 큰 우선순위를 가지는 프로세스를 찾기 위해서 현재 프로세스에서 몇 칸을 넘어서야하는지 계산하려고 함.
   헛수고에 코드가 더러워짐
4. 자꾸 오류가 생기는 문제로 항상 dequeue된 프로세스에 대해서 더 큰 우선순위가 있는지 체크하기로 함.

---

큐를 사용한 코드

 

package programmers;

import java.util.ArrayDeque;
import java.util.Queue;

public class 프로세스 {

    static class Solution {

        // 해당 프로세스의 우선도와 입력순서를 저장하는 클래스를 정의
        private static class Process {
            int priority, idx;

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

        }

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

            Queue<Process> queue = new ArrayDeque<>();

            // 큐에 각 요소들을 입력
            int idx = 0;
            for (int priority : priorities) {
                queue.offer(new Process(priority, idx++));
            }

            while (!queue.isEmpty()) {
                Process current = queue.poll();

                // 현재 꺼낸 프로세스보다 더 큰 프로세스가 있다면?
                if (hasHigherPriority(queue, current.priority)) {
                    // 꺼낸 프로세스를 다시 넣음
                    queue.offer(current);
                } 
                
                // 현재 꺼낸 프로세스가 제일 큰 프로세스라면?
                else {
                    // 해당 프로세스를 (answer+1)순위로 꺼냄
                    answer++;
                    // 해당 프로세스가 문제에서 요구하는 답이라면?
                    // 해당 프로세스가 몇 번째 순위로 꺼내졌는지 반환
                    if (current.idx == location) {
                        return answer;
                    }
                }
            }
            return answer;
        }

        // 나보다 우선순위가 큰 프로세스가 있는지 검사하는 메서드
        private boolean hasHigherPriority(Queue<Process> queue, int current) {

            // 큐에서 방금 꺼낸 프로세스를 제외한 모든 프로세스를 검사
            for (Process process : queue) {
                // 우선순위가 더 높은 프로세스가 있다면 true 반환
                if (process.priority > current) {
                    return true;
                }
            }
            // 없다면 false 반환
            return false;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // 테스트 케이스
        int[] priorities = {1, 1, 9, 1, 1, 1};
        int location = 1;

        int result = solution.solution(priorities, location);
        System.out.println("Result: " + result);
    }
}

 

---

 

우선순위큐를 사용한 코드

package programmers;


import java.util.Comparator;
import java.util.PriorityQueue;

public class 프로세스우선순위큐 {

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

        // 내림차순으로 정렬되도록 Comparator.reverseOrder()를 사용 (기본적으로 오름차순)
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

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


        while (!pq.isEmpty()) {
            for (int i = 0; i < priorities.length; i++) {
                // pq의 front가 입력 배열의 몇 번째 요소인지 찾아냄
                // 그 다음 반복은 해당 idx부터 반복 (반복문 break 없으니, 당연한 것)
                if (pq.peek() == priorities[i]) {
                    // 찾아냈다면 순위 갱신 (몇 번째로 실행되는지)
                    answer++;

                    // 해당 요소가 문제의 요구 사항이라면?
                    if (i == location) {
                        // 정답 반환
                        return answer;
                    }
                    // 해당 요소가 문제의 요구 사항이 아니라면?
                    else {
                        // dequeue 하고 다시 for 문으로 이동
                        pq.poll();
                    }
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] priorities = {1, 1, 9, 1, 1, 1};
        System.out.println(solution(priorities, 1));
    }

}

---

문제를 풀고 난 후

 

 

다른 블로그를 보고 우선순위큐로도 문제를 해결했는데, 너무 멋져서 상당히 자괴감이 든다. ㅜㅜ

사실 while 문 내부의 for문을 이해하지 못해서 엄청 시간을 소모했다.

우선순위큐가 안정 정렬이 아닌데 우선순위큐로 문제를 해결하는게 이해하기 어려웠다. 사실 안정된 정렬이여도 뭔가 이상하긴하다.

 

어쨌든, 문제를 해결한 것은 그게 포인트가 아니라 while 문 내부의 for문이 큰 역할을 하는 것이라는 것을 알았다.

주석을 참고한다면 빠른 시간내로 이해할 수 있는 쉬운 알고리즘이라고 생각함!

 

바보의 흔적 : https://okky.kr/questions/1498624?topic=questions&page=1

 

다들 화이팅, 나도 화이팅