[프로그래머스 / Java] 코딩테스트 연습: 프로세스 (스택 / 큐)

난이도: Level 2

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

프로그래머스

---

 

문제에 주어진 조건을 그대로 구현하면 된다.

큐를 사용해야 한다는 것도 문제에서 친절하게 알려준다.

우선 실행 대기 큐와 실행 리스트를 다음과 같이 선언한다.

 

    int answer = 0;     // location번째 프로세스가 실행되는 순서

    Queue<Process> ready = new LinkedList<>();  // 프로세스 실행 대기 큐

    List<Process> running = new ArrayList<>();  // 프로세스 실행 리스트

 

 

여기서 사용되는 Process 클래스는 다음과 같이 위치(location)와 우선순위(priority) 상태를 가지도록 정의한다.

 

    class Process {

        int location;   // 프로세스의 위치

        int priority;   // 프로세스의 우선순위

       

        Process(int location, int priority) {

            this.location = location;

            this.priority = priority;

        }

    }

 

 

실행 대기 큐에 다음과 같이 차례대로 i번째 위치와 우선순위가 priorities[i]인 프로세스 객체를 생성해서 삽입한다.

 

    // 실행 대기 큐에 위치와 우선순위를 상태로 가지는 프로세스 삽입

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

        ready.add(new Process(i, priorities[i]));

    }

 

 

문제에 주어진 아래의 프로세스 관리 규칙을 구현하면 된다.

이 과정을 실행 대기 큐가 빌 때까지 반복한다.

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

 

    // 실행 대기 큐가 비어있을 때까지 반복

    while (!ready.isEmpty()) {

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

        Process now = ready.poll();

        // 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있는지 판별

        boolean isMaxPriority = true;    

       

        // 실행 대기 큐에 있는 프로세스들을 모두 탐색

        for (Process next : ready) {

            // 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면

            //    방금 꺼낸 프로세스를 다시 큐에 넣습니다.

            if (next.priority > now.priority) {

                ready.add(now);     // 실행 대기 큐에서 꺼냈던 프로세스를 다시 삽입

                isMaxPriority = false;  // 우선순위 최댓값이 아니므로 false로 변경

                break;  // 실행 대기 큐를 더이상 탐색할 필요 없음

            }

        }

       

        // 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.

        if (isMaxPriority) {

            running.add(now);   // 실행 리스트에 실행 대기 큐에서 꺼냈던 프로세스 삽입

        }

    }

 

 

마지막으로 실행 리스트에 담겨있는 프로세스들을 하나씩 탐색해서 해당 프로세스의 location이 문제에 주어진 location과 같은지 비교하고, 같다면 해당 프로세스의 실행 리스트 인덱스 + 1을 리턴해주면 된다.

+1을 하는 이유는 리스트는 인덱스가 0부터 시작하지만, 문제에서는 순서가 1부터 시작하기 때문이다.

 

    // 실행 리스트에 있는 프로세스들을 모두 탐색

    for (int i = 0; i < running.size(); i++) {

        Process process = running.get(i);   // i번째 프로세스

        // 해당 프로세스의 위치가 문제에 주어진 위치와 같다면

        if (process.location == location) {

            answer = i + 1;     // location번째 프로세스는 i + 1번째로 실행

            break;      // 답을 찾았으므로 더이상 탐색할 필요 없음

        }

    }

       

    return answer;      // location번째 프로세스가 실행되는 순서 리턴

 

---

전체 코드

import java.util.*;
 
class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;     // location번째 프로세스가 실행되는 순서
        Queue<Process> ready = new LinkedList<>();  // 프로세스 실행 대기 큐
        List<Process> running = new ArrayList<>();  // 프로세스 실행 리스트
        
        // 실행 대기 큐에 위치와 우선순위를 상태로 가지는 프로세스 삽입
        for (int i = 0; i < priorities.length; i++) {
            ready.add(new Process(i, priorities[i]));
        }
        
        // 실행 대기 큐가 비어있을 때까지 반복
        while (!ready.isEmpty()) {
            // 1. 실행 대기 큐에서 대기중인 프로세스 하나를 꺼냅니다.
            Process now = ready.poll();
            // 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있는지 판별
            boolean isMaxPriority = true;    
            
            // 실행 대기 큐에 있는 프로세스들을 모두 탐색
            for (Process next : ready) {
                // 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 
                //    방금 꺼낸 프로세스를 다시 큐에 넣습니다.
                if (next.priority > now.priority) {
                    ready.add(now);     // 실행 대기 큐에서 꺼냈던 프로세스를 다시 삽입
                    isMaxPriority = false;  // 우선순위 최댓값이 아니므로 false로 변경
                    break;  // 실행 대기 큐를 더이상 탐색할 필요 없음
                }
            }
            
            // 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
            if (isMaxPriority) {
                running.add(now);   // 실행 리스트에 실행 대기 큐에서 꺼냈던 프로세스 삽입
            }
        }
        
        // 실행 리스트에 있는 프로세스들을 모두 탐색
        for (int i = 0; i < running.size(); i++) {
            Process process = running.get(i);   // i번째 프로세스
            // 해당 프로세스의 위치가 문제에 주어진 위치와 같다면
            if (process.location == location) {
                answer = i + 1;     // location번째 프로세스는 i + 1번째로 실행
                break;      // 답을 찾았으므로 더이상 탐색할 필요 없음
            }
        }
        
        return answer;      // location번째 프로세스가 실행되는 순서 리턴
    }
}
 
class Process {
    int location;   // 프로세스의 위치
    int priority;   // 프로세스의 우선순위
    
    Process(int location, int priority) {
        this.location = location;
        this.priority = priority;
    }
}