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

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

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

 

입력

priorities - 현재 실행 대기 큐에 있는 프로세스 중요도가 담긴 정 배열

location - 언제 실행되고 싶은지 알고 싶은 프로세스의 위치 (정수)

 

출력

return - 해당 프로세스가 몇 번째에 실행되는지 알려주는 정수 값

 

제한사항

• priorities의 길이는 1 이상 100 이하입니다.
  • priorities의 원소는 1 이상 9 이하의 정수입니다.
  • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
  • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

풀이

이 문제는 문제에서 볼 수 있듯이 큐 자료구조를 사용하여 풀어야 한다. 먼저 주어진 배열에서 가장 높은 우선순위를 가진 원소를 찾고 그 원소로 이동한다. 이 때 shift(), push() 메서드를 이용하여 큐처럼 구현한다. 그 원소에 도착했다면 꺼내고 이를 location인 원소를 찾을 때까지 반복한다. 말로만 이러면 구현하기 쉽지 않다. 따라서 이를 단계로 나누면 다음과 같다.

 

1. 주어진 배열의 원소가 없거나 타겟 원소가 location인 경우에 배열을 순회하는 것을 종료한다.
2. 배열의 가장 큰 숫자를 찾는다.
3. 나올 때까지 이동한다.
4. 가장 큰 숫자를 뺀다.
5. 결과를 도출한다.

직관적으로 읽기 위해 주어진 배열의 원소가 없는 것은 while문의 조건 priorities.length가 0일 때 종료하는 것으로 구현하였고 if문을 사용하여 타겟 원소가 location일 때 while 문을 종료하도록 구현하였다. 배열의 가장 큰 숫자를 찾는 것은 누가봐도 Math.max() 메소드였다. 나올 때까지 이동하는 것은 priorities.push(priorites.shift())를 이용하였다. 큐가 계속해서 바뀌기 때문에 location과 location의 원소를 어떻게 파악할까가 고민이었다. 예전에는 주어진 배열에 인덱스 배열을 추가하여 활용했지만 좀 더 location 자체를 location의 원소가 이동할 때마다 갱신하면 된다는 생각이 들어 이에 따라 구현하였다. 따라서 while문 안에는 조건문 4개가 필요하고 정리하면 아래와 같다.

priorities[0]이 배열의 최댓값	location이 0인 경우	결과
X	O	location = priorities.length -1; priorities.push(priorites.shift());
	X	location--; priorities.push(priorites.shift())
O	O	return ++answer;
	X	location--; priorities.shift(); 그 다음 최댓값 찾아 저장.

 

시간 복잡도는 while문을 최악으로 돌렸을 때 n+n-1+n-2+...+1이므로 n^2, 그리고 배열의 최댓값을 찾는 경우 n이므로 O(n^3)이다.

공간 복잡도는 priorites 배열과 몇 개의 변수만 사용하므로 O(n)이다.

코드

function solution(priorities, location) {
    var answer = 0;
    let maxV = Math.max(...priorities);
    
    while (priorities.length) {
        const target = priorities[0];
        
        if (target === maxV && location !== 0) {
            location--;
            ++answer;
            priorities.shift();
            maxV = Math.max(...priorities);
        } else if (target === maxV && location === 0) {
            return ++answer;
        } else if (target !== maxV && location !== 0) {
            location--;
            priorities.push(priorities.shift());
        } else {
            location = priorities.length - 1;
            priorities.push(priorities.shift());
        }
    }
    return answer;
}

 

• 매개변수를 수정할 수 있다는 사실이 신기하다. 왜일까.
• Array의 some() 메소드를 사용하는 게 빠를까 Math.max()를 사용하는 게 빠를까. 시간 복잡도는 O(n)으로 같은데 말이다.
  => Array의 some() 메소드가 더 빠르다. some 괄호 안의 조건에 부합하는 원소가 있다면 바로 true를 출력하기 때문이다.
• 공간복잡도를 늘리고 시간복잡도를 줄이는 것이 좋을까 반대가 좋을까.
• 코드를 읽기 좋게, 설명하기 쉽게 만드는 것이 가장 중요하다고 생각해서 지금은 이렇게 만들고 있다. 이런 뒤에 공통적인 부분을 묶을 수 있다면 줄이자. 혹은 리팩토링 책을 읽자.
• if 문의 중첩보다 if문을 4번 적는 것이 보기에는 쉽다. 그러나 중복을 최소한으로 줄이려면 중첩이 낫다. 뭐가 더 나은 코드일까.