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

문제 링크

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

문제 설명

내 풀이

function solution(priorities, location) {
    // index가 추가된 배열 만들기. 첫번째는 value, 두번째는 index
    let indexArray = priorities.map((v, idx) => [v, idx])
    // 최우선 순위를 알기 위해서 우선순위 Array를 제작
    const sortedArray = priorities.sort((a,b) => b-a);
    // 답안용 빈 배열
    const answerArray = [];
    
    // sortedArray가 다 없어질 때까지 동작
    while(sortedArray.length > 0) {
        let process = indexArray.shift();
        // 현재 존재하는 최우선 순위 값과 큐에서 꺼낸 우선순위 값이 같다면?
        if(process[0] == sortedArray[0]) {
            // 어차피 처리되었으니 우선순위는 알 필요가 없다.
            // 인덱스만 넣어주자.
            answerArray.push(process[1]);
            // 처리된 최우선 순위 값은 제거
            sortedArray.shift();
        }
        indexArray.push(process);
    }
    return answerArray.indexOf(location) + 1;
}

다른 사람의 풀이

function solution(priorities, location) {
    var arr = priorities.map((priority, index) => {
        return {
            index: index, priority: priority
        };
    });

    var queue = [];

    while(arr.length > 0) {
        var firstEle = arr.shift();
        var hasHighPriority = arr.some(ele => ele.priority > firstEle.priority);
        if (hasHighPriority) {
            arr.push(firstEle);
        } else {
            queue.push(firstEle);
        }
    }

    return queue.findIndex(queueEle => queueEle.index === location) + 1;
}

오늘 배운 점

처음 풀 때는 "우선순위 Queue로 풀면 되지 않을까??"라고 생각했지만, 조금 더 고민해 본 결과

• 우선 순위 Queue로 할 경우, 만약 더 높은 우선순위 프로세스가 들어온다면, 한 순서씩 뒤로 밀리지, 다시 Queue로 돌아가는 것이 아니다.
• 따라서 사용하면 안된다.

라고 판단하였습니다.

두 번째로 많은 분들이 arr.some을 사용했는데, some 메서드를 알아보면

some() 메서드는 배열 안의 어떤 요소라도 주어진 판별 함수를 적어도 하나라도 통과하는지 테스트합니다. 만약 배열에서 주어진 함수가 true을 반환하면 true를 반환합니다. 그렇지 않으면 false를 반환합니다. 이 메서드는 배열을 변경하지 않습니다.

이런 식으로 정리되어 있습니다.

그러나 개인적으로 some Method를 사용한다면, 반복문 안에 또 다시 반복문이 돌기 때문에 시간복잡도가 O(N^2)가 되지 않을까?? 라는 생각을 하였습니다.

따라서 최우선순위 배열을 알 기 위해서 SortedArray를 직접 제작하였으며, 최우선 순위가 일치한다면 push를 이용해서 첫 인덱스를 제거하는 방법을 사용했습니다.

참고

Array.prototype.some() - JavaScript | MDN