[프로그래머스][Java] 프로세스 - level 2

 

 

문제 보기

프로그래머스

 

 

풀이 방법

그냥 큐, 혹은 배열을 사용하려 하면 코드가 길어지지만 Java에서는 우선순위 큐(PriorityQueue)를 제공하기 때문에 비교적 짧은 코드로 구현이 가능하다.

 

1. PriotityQueue에 옮겨 닮기

class Solution {
    public int solution(int[] priorities, int location) {
    	// 0. Priority Queue에 옮겨 담기.
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int priority : priorities) {
            pq.add(priority);
        }
    }
}

 

우선순위 큐는 제일 먼저 추가된 원소 대신, 우선순위가 제일 높은 원소를 가장 먼저 꺼내온다.

우선순위를 오름차순, 내림차순 중 무엇으로 측정할지는 PriorityQueue의 생성자에 주입할 수 있다.
여기서는 내림차순(제일 큰 값부터 꺼내기)을 사용하기 위해 Collections.reverseOrder()를 주입해 주었다.

 

Java 우선순위 큐 참고

[Java/자료구조] 선형구조 - 큐(Queue) 이해하기: 일반 큐, 우선순위 큐(Priority Queue) 이해하기

 

 

2. 상황 구현하기

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

 

1~3번까지 조건을 살펴보자.

먼저 현재 queue 내에서 우선순위가 가장 높고, 가장 앞에 있는 프로세스를 꺼낸다.
그리고 그다음 우선순위가 가장 높고, 가장 앞에 있는 프로세스를 꺼낸다.
여기서 가장 앞이란 방금 꺼낸 프로세스의 바로 뒤가 된다.

그러다 주어진 위치의 프로세스를 꺼내게 되면, 지금까지 꺼낸 프로세스 수를 return 하면 된다.

 

        int count = 0;
        while (!pq.isEmpty()) {
           for(int i = 0; i < priorities.length; i++) {
               if(priorities[i] == pq.peek()) {
                   pq.poll();
                   count++;

                   if(i == location) {
                       return count;
                   }
               }
           }
        }

 

최악의 경우 queue의 원소를 전부 제거할 때까지 순회해야 한다.

우선순위 큐 만으로 문제를 풀려고 하면 프로세스의 위치를 알 수 없게 된다.
그래서 바로 poll하지 않고 배열 순회를 통해 우선순위가 가장 높은 프로세스를 만나면 그 때 제거를 진행한다.
제거한 프로세스의 index가 location과 동일하면 그대로 지금까지 꺼낸 프로세스 수(count)를 return 하였다.

for문은 index의 끝까지 도달하더라도 while문 안에서 계속 뱅글뱅글 돌 것이다.

 

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int priority : priorities) {
            pq.add(priority);
        }

        int count = 0;
        while (!pq.isEmpty()) {
           for(int i = 0; i < priorities.length; i++) {
               if(priorities[i] == pq.peek()) {
                   pq.poll();
                   count++;

                   if(i == location) {
                       return count;
                   }
               }
           }
        }
        return count;
    }
}

 

 

GitHub 링크

CodingTest_AutoSave/프로그래머스/2/42587. 프로세스 at 1e7050d0759a27e02e3ebd7cd3174e8d7c74e924 · MetroDefro/CodingT