[프로그래머스/42587] 프로세스

16 Jan 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이
  • 두 번째 풀이

☑️ 문제

프로그래머스 42587

☑️ 풀이

우선순위를 내림차순으로 정리한 배열과 Queue를 사용하여 순차적으로 탐색하는 방식을 사용했다.

첫 번째 풀이

1. Queue에 주어진 프로세스를 저장할 때, 우선순위 + 인덱스 형식으로 저장하도록 하였다.
2. priorities 배열을 내림차순으로 정렬한 arr 배열을 먼저 준비한다. → 현재 출력해야할 우선순위를 추적하기 위함
3. Queue에서 프로세스를 꺼내서 현재 가장 높은 우선순위와 비교 후,
   • 동일하면 출력 순서(answer)를 증가시킨다.
   • 동일하지 않으면 Queue에 다시 삽입한다.
4. 출력된 프로세스가 원하는 location과 동일하면 종료한다.

//시간: 6.17ms
//메모리: 90.5MB

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < priorities.length; i++) {
            String s = Integer.toString(priorities[i]) + Integer.toString(i);
            queue.offer(Integer.parseInt(s));
        }

        Integer[] arr = Arrays.stream(priorities).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder()); // 내림차순 정렬

        int idx = 0;
        int answer = 0;
        while (!queue.isEmpty()) {
            String str = Integer.toString(queue.poll());
            int priority = Integer.parseInt(str.substring(0, 1)); // 우선순위
            int qLocation = Integer.parseInt(str.substring(1)); // 위치

            if (priority == arr[idx]) {
                idx++;
                answer++;
                if (location == qLocation) {
                    break;
                }
            } else {
                queue.offer(Integer.parseInt(str));
            }
        }

        return answer;

    }
}

• 위의 풀이는 문자열 처리가 너무나도 비효율적이라, 아래 코드로 다시 리팩토링했다.

두 번째 풀이

• 프로세스의 우선순위와 위치를 문자열 “우선순위,위치”로 저장해 Queue에 삽입하는 방식을 사용했다.
  • split(”,”) 메서드를 이용하여 문자열을 분리하여 처리한다.

//시간: 19.48ms
//메모리: 79.3MB

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < priorities.length; i++) {
            String s = priorities[i] + "," + i;
            queue.offer(s);
        }

        Integer[] arr = Arrays.stream(priorities).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder()); // 내림차순 정렬

        int idx = 0;
        int answer = 0;
        while (!queue.isEmpty()) {
            String str = queue.poll();
            String[] strArr = str.split(",");
            int priority = Integer.parseInt(strArr[0]); // 우선순위
            int qLocation = Integer.parseInt(strArr[1]); // 위치

            if (priority == arr[idx]) {
                idx++;
                answer++;
                if (location == qLocation) {
                    break;
                }
            } else {
                queue.offer(str);
            }
        }

        return answer;

    }
}