[Programmers] 프로세스 JAVA

반응형

728x90

[Programmers] 프로세스 - LV 2 

---

접근

• 큐

---

풀이

프로세스를 우선순위에 맞춰 실행하였을 경우 특정 위치의 프로세스가 몇 번째에 실행되는지 구하는 문제이다. 스택과 큐 파트에 있는 문제인데 설명부터 실행 대기 큐에 존재하는 프로세스로부터 수행되기 때문에 큐를 사용하는 문제이다. 큐에서 꺼낸 프로세스보다 우선순위가 높은 프로세스가 큐에 존재하는 경우 프로세스를 다시 큐에 넣게 되고 한 번 실행한 프로세스는 그대로 종료된다. 큐에 특정 위치의 프로세스가 몇 번째 실행되는지 구해야 하는 문제이기 때문에 우선순위와 위치를 같이 관리해주어야 한다.

    private class Process {
        int location;
        int priority;

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

딱히 다른 생각이 나지 않았던 것도 있고 자바스럽게 우선순위와 위치를 함께 관리하기 위한 객체를 생성해 줬다. 

    public int solution(int[] priorities, int location) {
        Queue<Process> q = new LinkedList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);

        for (int i = 0; i < priorities.length; i++) {
            Process process = new Process(i, priorities[i]);

            q.offer(process);
            pq.offer(priorities[i]);
        }

프로세스가 들어있는 실행 대기 큐의 역할을 할 기본 큐와 우선순위 관리를 위한 우선순위 큐를 각각 사용해 줬다. 실행 대기 큐에는 객체를 만들어 큐에 넣고 우선순위 큐에는 우선순위 값만 넣어줬다. 

	int answer = 0;
        
        while (!q.isEmpty()) {
            Process process = q.poll();

            if (!pq.isEmpty() && process.priority == pq.peek()) {
                pq.poll();
                answer++;

                if (process.location == location) {
                    return answer;
                }
            } else {
                q.offer(process);
            }
        }
        return 0;
    }

실행 대기 큐에서 프로세스를 뽑아낸 뒤 해당 프로세스가 현재 실행되어야 할 프로세스가 맞는지 검사한 뒤 아니라면 다시 큐에 집어넣고 맞다면 실행 처리를 해준다. 실행 처리로는 우선순위 큐의 값을 하나 뽑아주고 실행되었다는 의미로 answer 값을 증가시킨 뒤 현재 실행시킨 프로세스가 찾고자 하는 위치의 프로세스인지 확인하고 맞다면 answer를 반환한다. 아니라면 해당 위치의 프로세스를 찾을 때까지 계속 반복하게 된다. 

---

location 관리

위에서 풀었던 방법은 우선순위에 중점을 두고 푸는 방법인데 다른 사람의 풀이에 가장 많은 댓글이 있던 location을 관리해 푸는 코드를 가져왔다. 큐에 우선순위와 위치를 같이 관리하지 않고 해결한 코드였는데 처음엔 location을 관리한다는 게 무슨 소린지 이해가 가지 않았다.

 

위의 코드는 예를 들어 2번째에 위치한 프로세스가 A라면 현재 프로세스들을 단순히 우선순위에 맞게 실행하며 실행한 뒤 해당 프로세스가 A였는지를 검사하는 방법이라면 location을 관리하는 이 코드는 현재 프로세스가 실행되는 것에 중점을 두는 게 아닌 프로세스 A의 위치가 어떻게 변하는지에 대해 중점을 두고 풀어진 코드였다.

//우선순위 실행 중점
프로세스 A

실행 프로세스 = B
if(프로세스 B == 프로세스 A) -> false 
.
.
.
실행 프로세스 = A
if(프로세스 A == 프로세스 A) -> true -> return

//location 중점
[C, D, A, E, B]
프로세스 A 현재 위치 = 2

실행 프로세스 = C
프로세스 A 현재 위치 -> 1
[D, A, E, B]

실행 프로세스 = D 
프로세스 A 현재 위치 -> 0
[A, E, B] 

실행 프로세스 = A
프로세스 A 현재 위치 -> -1 -> return

//A가 현재 실행 될 차례가 아니라면
[A, E, B] 프로세스 A 현재 위치 -> 0
큐의 맨 뒤로 -> [E, B, A]
프로세스 A 현재 위치 -> 2

위와 같이 우선순위에 맞춰 프로세스들은 실행하나 A의 위치를 매번 추적하여 프로세스 A가 어디 있는지 체크한다. 큐에 우선순위와 위치를 함께 관리하지 않다 보니 목표 프로세스에 대해서만 따로 관리를 하는 느낌이라고 보면 된다.

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

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities);
        int size = priorities.length-1;

큐에는 우선순위 값만 순서대로 넣어 초기 실행 위치를 보장한다. 그리고 배열 자체를 정렬해 우선순위를 관리하게 된다. 

	while(!que.isEmpty()){
            Integer i = que.poll();
            if(i == priorities[size - answer]){
                answer++;
                l--;
                if(l <0)
                    break;
            }else{
                que.add(i);
                l--;
                if(l<0)
                    l=que.size()-1;
            }
        }

        return answer;
    }

배열을 오름차순으로 정렬했기 때문에 배열의 마지막 인덱스 부터 접근해 우선순위 큐를 사용하는 대신 실행 순서를 체크했다. 현재 프로세스가 실행될 순서가 맞다면 answer를 증가시키고 location 값을 감소시킨다. location 값을 감소시키는 이유는 단순하게 큐의 맨 앞에서 프로세스가 뽑아져 나갔으니 처음에 2의 위치에 있던 프로세스라면 1로 이동했을 것이기 때문에 감소시켜 주는 것이다. location의 값이 0보다 작다면 목표로 하던 프로세스가 실행이 되었다는 뜻으로 실행 순서를 반환하게 된다. 만약 현재 프로세스가 실행 순서가 아니라면 다시 큐에 집어넣고 동일하게 프로세스 자체는 뽑혔던 상태이기 때문에 location 값을 줄여 해당 프로세스가 앞으로 전진시켜 준다. 만약에 location의 값이 0 보다 작아졌다면 해당 프로세스가 뽑혔다가 실행될 순서가 아니라 다시 큐에 들어간 경우이므로 lcoation을 큐의 맨 마지막으로 변경해 주게 된다. 

---

전체 코드

import java.util.*;

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

        public Process(int location, int priority) {
            this.location = location;
            this.priority = priority;
        }
    }
    
    public int solution(int[] priorities, int location) {
        Queue<Process> q = new LinkedList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);

        for (int i = 0; i < priorities.length; i++) {
            Process process = new Process(i, priorities[i]);

            q.offer(process);
            pq.offer(priorities[i]);
        }

        int answer = 0;
        
        while (!q.isEmpty()) {
            Process process = q.poll();

            if (!pq.isEmpty() && process.priority == pq.peek()) {
                pq.poll();
                answer++;

                if (process.location == location) {
                    return answer;
                }
            } else {
                q.offer(process);
            }
        }
        return 0;
    }
}

 

location 관리

import java.util.*;

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

        Queue<Integer> que = new LinkedList<Integer>();
        for(int i : priorities){
            que.add(i);
        }

        Arrays.sort(priorities);
        int size = priorities.length-1;



        while(!que.isEmpty()){
            Integer i = que.poll();
            if(i == priorities[size - answer]){
                answer++;
                l--;
                if(l <0)
                    break;
            }else{
                que.add(i);
                l--;
                if(l<0)
                    l=que.size()-1;
            }
        }

        return answer;
    }
}