Programming/JAVA

[프로그래머스] 프로세스(level2, Queue)

gayeon_ 2024. 9. 4. 10:38

문제 설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

 

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.

2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다. 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.

3.한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

 

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

  • priorities의 길이는 1 이상 100 이하입니다.
    • priorities의 원소는 1 이상 9 이하의 정수입니다.
    • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
  • location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
    • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

 

입출력 예

priorities  location  return
[2, 1, 3, 2] 2 1
[1, 1, 9, 1, 1, 1] 0 5

 

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

 

예제 #2

6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

 

 

내 코드(실패)

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        return answer;
        
        Queue<Integer> q = new LinkedList<>();
        
        for(int i = 0; i < priorities.length; i++){
            q.offer(priorities[i]);
        }
        
        int l = location;
        int e = 0;
        
        // 찾고 싶은 우선순위가 큐의 맨 앞으로 오도록 하기
        for(int j = 0; j < l; j++){
            e = q.poll();
            q.offer(e);
        }
    }
}

 

찾고 싶은 우선순위가 큐의 맨 앞으로 오도록 하는 것까지는 작성했지만 실행 순서를 어떻게 계산하고 출력해야 하는지 모르겠어서 마저 작성을 못했다.

 

 

성공 코드

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int solution(int[] priorities, int location) {
        // 우선순위 큐 선언
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        int answer = 0;

        // 우선순위 큐에 우선순위 요소 추가
        for (int i : priorities) {
            queue.offer(i);
        }

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 기존 우선순위 배열 순회
            for (int i = 0; i < priorities.length; i++) {
                // 현재 작업의 위치 찾기
                if (queue.peek() == priorities[i]) {
                    queue.poll();
                    answer++;

                    // 현재 작업이 location과 같으면 answer 반환
                    if (location == i) {
                        return answer;
                    }
                }
            }
        }

        return answer;
    }
}

 

찾아보니 그냥 큐가 아닌 우선순위 큐가 있었다.

우선순위 큐를 선언할 때는 reverseOrder() 메서드로 내림차순으로 정렬할 수 있다.

그래서 큐에는 정수형 배열인 priorities가 내림차순으로 정렬된 상태로 저장된다.

 

priorities를 앞에서부터 순회하며 큐의 맨 앞 요소(우선순위가 가장 높은 요소)의 위치를 찾는다.

 

현재 작업의 우선순위가 큐의 가장 앞에 있는 우선 순위와 같다면 큐에서 해당 우선 순위 요소를 제거하고 answer를 증가해 현재 작업이 처리된 순서를 기록한다.

 

만약 현재 배열의 인덱스와 location이 같다면 바로 answer를 반환해 작업이 처리된 순서를 출력한다.