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

알고리즘 고득점 Kit의 스택&큐 문제 중 하나인 '프로세스'를 자바로 풀어보았다. 

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

프로그래머스

 

 

 우선 큐를 만들어서 인덱스를 모두 넣어주는 것으로 풀이를 시작했다. 그다음, 현재 남아있는 인덱스 중 최댓값을 찾는 것으로 초기 설정을 마쳤다. 그다음 while문을 통해서, 현재 poll 된 인덱스의 priority 값이 최댓값이 아니면 다시 넣어주고, 최댓값이라면 poll 된 채로 두고, cur_max를 그다음 max 값으로 바꾸는 작업을 반복한다. 현재 poll 된 인덱스의 priority 값이 최댓값인데, 인덱스 역시 location과 같다면 while문을 종료해 준다. 그리고 마지막으로 주어진 element의 개수였던 priorities array의 길이와 현재 queue 내에 남아있는, 즉 아직 삭제되지 않은 값들의 개수의 차를 구해주면, location에 위치한 element가 몇 번째로 삭제되는지를 알 수 있다. 

import java.util.*;

class Solution {
    // 현재 queue에 남은 인덱스들로 priorities 내 최대값 찾기
    public int find_max(LinkedList<Integer> queue, int[] priorities) {
        int max = 0;
        for (int idx : queue) {
            if (priorities[idx] > max)
                max = priorities[idx];
        }
        return max;
    }
    
    public int solution(int[] priorities, int location) {
        // 초기 변수 설정
        int answer = 0;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < priorities.length; i++) queue.offer(i);
        int cur_max = find_max(queue, priorities);
        
        // location이 poll되는 순서 찾기
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (priorities[cur] != cur_max) {
                queue.offer(cur);
            } else {
                if (cur == location) break;
                cur_max = find_max(queue, priorities);
            }
        }
        return priorities.length - queue.size();
    }
}

 

 

 문제를 푼 후 다른 사람들의 풀이를 확인하니 독특한 풀이가 많았다. 특히 기억에 남는 풀이는 location을 이동해가며 푸는 풀이였다. 처음에 properties를 queue에 넣고, properties 배열 자체는 정렬을 한다. 그리고 location을 움직여가며 찾는 것이다. 이 방법을 쓰면 내가 위에서 풀이한 것처럼 매번 max값을 확인하느라 이중 loop를 돌 필요가 없었다. 그래서 이를 기반으로 한 번 더 코드를 작성해 보았다. 

 우선 처음에 que에 priorities 값 자체를 넣는다. 그리고 priorities를 sort 해준다. 이렇게 되면 queue에는 priorities가 처음 순서대로 남게 되고, priorities 배열에는 오름차순으로 남게 된다.

 그리고 while 문으로 que 내의 값을 하나씩 poll 해준다. 이 값이 이제 priorities의 배열 내 남아있는 마지막 값과 같은지만 확인해주면 최댓값과 같은지 확인할 수 있다. answer값이 몇 개를 삭제해 줬는지를 담고 있기 때문에 len에서 answer값을 뺀 인덱스에 위치한 priorites 배열 값이 현재값과 같은지 확인해 주고, 만약 같으면 answer을 하나 더해준다. 다르면 다시 que에 현재갑을 넣어준다.

여기서 중요한 점은 둘 모두 location을 하나씩 빼준다는 것인데, que에서 맨 앞에 있던 값이 하나씩 빠지는 것이므로, 우리가 찾고자 하는 값의 location이 점점 앞으로 하나씩 당겨진다. 그래서 location을 하나씩 빼주는 것이다. 만약 현재값이 최대값인 동시에 location이 0이라면 그건 현재 빼고 있는 값이 우리가 찾고 있는 값이라는 뜻이므로 반복문을 바로 중단해 주면 된다. 만약 현재값이 최댓값이 아니면서 location이 음수가 된다면, 그건 우리가 찾는 값이 다시 add 되었다는 뜻이므로, location을 현재 queue의 사이즈에 1을 뺀 값으로 설정해 준다. 

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<Integer> que = new LinkedList<Integer>();
        int len = priorities.length;
        for (int i = 0; i < len; i++) que.add(priorities[i]);
        len--;
        Arrays.sort(priorities);
        
        while (!que.isEmpty()) {
            int cur = que.poll();
            if (cur == priorities[len-answer]) {
                answer++;
                if (location == 0) break;
                location--;
            } else {
                que.add(cur);
                location--;
                if (location < 0)
                    location = que.size() - 1;
            }
        } 
        
        return answer;
    }
}