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

---

프로그래머스 Lv2 - 프로세스 문제

프로그래머스 알고리즘 고득점 Kit 카테고리의 스택/큐 문제 중 레벨 2 프로세스 문제를 풀이했다.

로직은 아래와 같다

1. 문제 풀이에 필요한 Process 클래스(필드 및 생성자) 작성
2. 우선순위가 높은 순서로 값을 담을 리스트, 정답을 추출할 리스트, 문제 풀이에 사용할 큐 선언
3. 인자로 주어진 priorities 배열을 순회하며 큐 및 우선순위 내림차순 리스트에 초기값 할당
4. while문 내에서 큐에서 값을 하나씩 빼내면서 뺀 값이 가장 큰 우선순위와 같다면 정답 리스트에 추가, 아니라면 다시 큐에 꼬리부분에 삽입
5. 마지막 for문을 통해서 정답 리스트를 순회하며 현재 반복되고 있는 Process 객체가 최초에 인자로 주어진 location과 같은 객체라면(p.isTarget == true) 정답 변수에 i + 1(순서이기 때문에 인덱스 + 1)을 하고 반복 종료

최대한 시간복잡도를 줄이기 위해 중첩 for문을 사용하지 않고 풀이해보았다.
이번 문제는 왜인지 효율성 테스트가 없던데 아마 문제 조건의 범위가 크지 않아서 어떻게 알고리즘을 짜든 소요 시간에는 큰 차이가 없어 효율성 테스트가 없는 듯 하다..!

Processes.java

package com.example.Programmers.Lv2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 프로그래머스 Lv2 - 프로세스 문제
 * 스택/큐 카테고리
 */
public class Processes {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        List<Integer> maxValList = new ArrayList<>();
        List<Process> answerList = new ArrayList<>();
        Queue<Process> queue = new LinkedList<>();

        // 큐 초기화
        for (int i = 0; i < priorities.length; i++) {
            maxValList.add(priorities[i]);
            if (i == location) {
                queue.add(new Process(priorities[i], true));
            } else {
                queue.add(new Process(priorities[i], false));
            }
        }

        // 우선순위 값이 높은 순서대로(내림차순) 정렬
        Collections.sort(maxValList, Collections.reverseOrder());

        while (!queue.isEmpty()) {
            Process process = queue.poll();
            // 현재 큐의 top부분의 우선순위가 최고 높은 우선순위와 같다면 정답 리스트에 추가
            if (process.priority == maxValList.get(0)) {
                answerList.add(process);
                // 그 다음 높은 값을 리스트 맨 앞에두기 위해 맨 앞 인덱스 삭제
                maxValList.remove(0);
                // 같지 않다면 다시 큐에 삽입
            } else {
                queue.add(process);
            }
        }

        for (int i = 0; i < answerList.size(); i++) {
            Process p = answerList.get(i);
            if (p.isTarget == true) {
                answer = i + 1;
                break;
            }
        }
        return answer;
    }
}

class Process {
    public int priority;
    public boolean isTarget;

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

ProcessesTest.java

package com.example.Programmers.Lv2;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class ProcessesTest {
    @Test
    public void testProcesses() {
        Processes processes = new Processes();

        int result1 = processes.solution(new int[] { 2, 1, 3, 2 }, 2);
        int result2 = processes.solution(new int[] { 1, 1, 9, 1, 1, 1 }, 0);

        assertEquals(1, result1);
        assertEquals(5, result2);
    }
}