[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

1. 문제설명

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

---

2. 접근방식

2-1. 배열 쪼개기 (추천하지 않음❌)

보자마자 최대값을 찾아서 최대값의 인덱스를 기준으로 배열을 쪼개서 다시 붙이면 될 거 같다고 생각했다. priorities 배열를 순회하면서 우선순위 max값을 찾고, 그 값의 인덱스를 기준으로 배열을 두 개로 쪼갠 다음, 앞 뒤로 이어서 붙이는 것이다. 되게 쉽게 풀 줄 알았는데 생각보다 어려웠고 솔직히 계속 실패했다. 배열 쪼개는 메서드를 구글에서 찾아가면서 코드를 쓰는데 써 내려 갈수록 코드가 너무 길어지고 생소했다. 그래서 이 코드는 굉장히 비효율적인 코드라고 생각했다.
 

import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        // 1. 최대값의 인덱스 찾기
        int maxIndex = 0;
        for (int i = 1; i < priorities.length; i++) {
            if (priorities[i] > priorities[maxIndex]) {
                maxIndex = i;
            }
        }

        // 2. 배열을 최대값 인덱스를 기준으로 나누기
        int[] firstPart = Arrays.copyOfRange(priorities, 0, maxIndex);
        int[] secondPart = Arrays.copyOfRange(priorities, maxIndex, priorities.length);

        // 3. 배열을 두 부분으로 나눈 뒤 재결합 (두 번째 부분이 앞에, 첫 번째 부분이 뒤에)
        int[] mergedArray = new int[priorities.length];
        System.arraycopy(secondPart, 0, mergedArray, 0, secondPart.length);
        System.arraycopy(firstPart, 0, mergedArray, secondPart.length, firstPart.length);

        // 4. 원래 `location` 값의 새로운 인덱스 찾기
        int newIndex = -1;
        int originalValue = priorities[location];
        for (int i = 0; i < mergedArray.length; i++) {
            if (mergedArray[i] == originalValue) {
                newIndex = i;
                break; // 가장 첫 번째로 나오는 값의 인덱스 반환
            }
        }

        // 결과 반환
        return newIndex;
    }
}

 
아.... 이 방식은 아무리 해도 안되는 것 같다.
 
왜냐하면 우선순위에 같은 숫자가 너무 많아서 반환받을 값을 특정 해 주기 어려운 게 사실이다. 
 
priorities 배열에 동일한 값이 여러 번 나타나는 문제 때문에 mergedArray에서 올바른 인덱스를 반환하지 못하고 있다. 내가 써 내려 가면서 이 코드는 답이 없다고 생각한 순간이 있는데, 거의 끝에 쯤 originalValue를 반환하는 코드를 적을 때이다. 첫 번째 값을 찾아 올 수 밖에 없다는 걸 깨닳았을 때 위에 코드는 포기해야겠다는 생각이 들었다. 그래서 다시 원점으로 돌아가서 생각을 해 보았다. 
 
여전히 배열로 푸는 방법과 큐를 사용해서 푸는 방법이 있다.

---

3. 문제 풀이

3-1. 큐 안 쓰고 배열로 풀기

cnt선언 : location이 몇 번째로 처리되었는지 담아줄 변수
우선순위가 가장 높은 것이 priorities 배열의 맨 앞에 있는 요소(priorities[0])인지 확인한다.
 

priorities[0] 우선순위가 max가 아닐 때 

맨 앞에 우선순위 max값이 올 때까지 priorities[0] 을 temp 변수에 담아 주고, priorities[0]을 맨 뒤로 보내준다. 그리고 나머지 값을 한 칸 씩 앞으로 당겨 준다. 이 때, 요소가 이동해 줄때마다 location도 하나씩 감소해준다. 
 

priorities[0] 우선순위가 max가 맞을 때

1. cnt++ 증가: 프로세스를 하나 처리할 때마다 cnt를 증가시킨다. 이 변수는 현재까지 몇 개의 프로세스를 처리했는지 반환한다.
2. if (location == 0) 조건: 만약 location이 0이면, 지금 처리하려고 하는 프로세스가 내가 찾는 프로세스이다. 이때 cnt를 반환하면 이 문서가 몇 번째로 처리되었는지 알 수 있다. 

만약 priorities = [2, 1, 3, 2]이고 location = 2라면, location이 가리키는 프로세스는 3이다. 3보다 우선순위가 높은 프로세스가 없으므로 3을 첫번째로 처리한다. 그래서 cnt는 1이 된다. location == 0 체크하는 이유는 만약 처리한 프로세스가 내가 추적하는 프로세스(인덱스 2)라면, 이때 cnt를 반환해서 3이 1번째로 출력되었다고 알려 주기 위해서이다. 

import java.util.Arrays;

class Solution {
    public int solution(int[] priorities, int location) {
        int cnt = 0; // 프로세스가 처리된 순서

        while (true) {
            // 가장 앞에 있는 프로세스가 가장 높은 우선순위인지 확인
            int first = priorities[0];
            
            // 우선순위가 더 높은 것이 있는가? 불리언 타입 선언하고
            // 초기값 false로 세팅
            boolean higherPriorityExist = false;
            
            // loop 돌면서 prioiritis[i] 가 첫번째 요소보다 큰 지 확인
            // 만약에 현재 요소 priorities[0]보다 크면
            // higherPriorityExist는 true; 이고 break;
            for (int i = 1; i < priorities.length; i++) {
                if (priorities[i] > first) {
                    higherPriorityExist = true;
                    break;
                }
            }
            
            if (higherPriorityExist) {
                // 우선순위가 더 높은 프로세스가 있으면 맨 뒤로 이동
                // 첫 번째 요소를 temp에 담아 준다.
                int temp = priorities[0];
                // 배열 요소들을 한 칸씩 앞으로 이동
                for (int i = 1; i < priorities.length; i++) {
                    priorities[i - 1] = priorities[i];
                }
                // 배열 끝에 temp에 담아 두었던 값 넣기
                priorities[priorities.length - 1] = temp;
                
                
                if (location == 0) { // 맨 앞에서 이동했으면 location도 맨 뒤로 이동
                    location = priorities.length - 1;  
                } else { // 맨 앞에서 하나씩 이동시킨 후 위치를 하나씩 감소
                    location--;  
                }
            } else {
            	// higherPriorityExist가 false일 때 실행
                // 즉, 배열의 첫 번째 요소가 가장 높은 우선순위를 가지는 경우
                // 우선순위가 가장 높은 프로세스가 맨 앞에 있으면 프로세스 처리
                //맨 앞에 있는 프로세스가 처리되었으므로 cnt를 증가시켜 
                // 처리된 프로세스의 순서를 기록
                cnt++;
                if (location == 0) { // 찾는 프로세스가 맨 앞에 있는 경우
                    return cnt;  // 카운트 반환
                }
                
                // 맨 앞의 프로세스를 처리했기 때문에 배열을 앞으로 한 칸씩 이동
                for (int i = 1; i < priorities.length; i++) {
                    priorities[i - 1] = priorities[i];
                }
                // 배열의 마지막 요소를 0으로 설정하여 처리된 프로세스를 제거된 것으로 표시
                priorities[priorities.length - 1] = 0; 
                // location도 1씩 감소
                location--;
            }
        }
    }
}

 
 
location은 우리가 추적하는 프로세스의 위치를 가리키긴다. location--은 배열이 앞으로 이동했기 때문에 location도 한 칸 앞으로 줄어들도록 조정해 주는 것이고, 만약 location이 0이 아니었다면, 계속 감소시켜 locaiton이 0이 될 때 까지 반복한다. 그 때마다 cnt가 1씩 증가 하면서 location이 가리키는 프로세스가 몇 번째로 처리되는 지 기록한다.
 

3-2. 큐로 풀기

큐에 우선순위 요소들을 내림차순으로 추가한다다.
큐가 빌 때 까지 배열을 돌면서 queue.peek()값의 인덱스를 찾는다.
현재 작업이 location과 같으면 cnt 반환
 

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
    
    	// 내림차순 큐 선언
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        int cnt = 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(); // 우선순위 큐에서 제거
                    cnt++; // 프로세스 순서 증가
                    
                    // 찾고 있는 프로세스가 현재 프로세스이면 cnt 반환
                    if (location == i) {
                        return cnt;
                    }
                }
            }
        }
        return cnt;
    }
}

 
Queue에 배열요소를 추가할 때 queue.offer()을 해 준 이유는 queue.add()메서드보다 안정성 측면에서 우수하기 때문이다. add()는 삽입이 실패할 경우 예외를 던지는 반면, offer()는 실패할 경우 false를 반환하여 예외를 처리하지 않고 더 안전하게 큐에 요소를 추가 수 있다. 특히 큐의 크기가 제한적일 때 offer()를 쓰는 것이 좋다.
 

---

 

4. 큐에서 처리되는 로직

에제2의 예시 배열 [1, 1, 9, 1, 1, 1]을 큐에 집어 넣은 모습을 구글 슬라이드로 그려 보았다. original 배열 priorities의 인덱스도 함께 표시해 주었다. Prioirity Queue를 내림차순 정렬하면, 같은 숫자끼리는 어떻게 될까? 내림차순은 유지되나 같은 값에 대해서는 삽입된 순서가 유지된다. 큐는 FIFO 특성을 가지고 있기 때문이다. 
 

• 배열 priorities = [1, 1, 9, 1, 1, 1]
• location = 5 (배열의 마지막 인덱스)
• cnt = 0

우선순위 큐는 내림차순으로 정렬 queue = [9, 1, 1, 1, 1, 1]
큐에서 값을 꺼내면서 카운트를 증가시키고, 각 값을 처리한 후 location이 현재의 배열 인덱스와 같으면 카운트를 반환
 

Priorities	p[0]	p[1]	p[2]	p[3]	p[4]	p[5]
	1	1	9	1	1	1
queue 처리 로직
i			2	3	4	5
queue.peek()	9	9	9	1	1	1
priorities[i]	1	1	9	1	1	1
location	5	5	5	5	5	5
cnt	0	0	1	2	3	4

 

1. 첫 번째 회차 (queue.peek() == priorities[2]):
   
   • cnt = 1 (카운트 1 증가)
   • location은 여전히 5, i는 2이므로 불일치
2. 두 번째 회차 (queue.peek() == priorities[3]):
   
   • cnt = 2 
   • location은 여전히 5이고, i는 3이므로 불일치
3. 세 번째 회차 (queue.peek() == priorities[4]):
   • cnt = 3
   • location은 여전히 5이고, i는 4이므로 불일치
4. 네 번째 회차 (queue.peek() == priorities[5\):
   
   • cnt = 4
   • location은 5이고, i는 5이므로 location과 i가 일치
   • 이때 cnt를 반환

---

5. 같은 유형 문제 (스택/큐)

 

[프로그래머스] (Java) 주식가격 (스택/큐)

[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)

[프로그래머스] (Java) 올바른 괄호 문제풀이 (스택/큐)

[프로그래머스] (Java) 기능개발 (스택/큐)

[프로그래머스] (Java) 같은 숫자는 싫어 문제 풀이 (스택/큐)