[프로그래머스][Javascript] 완주하지 못한 선수

문제

프로그래머스 해시 문제 - 완주하지 못한 선수

문제 설명

참가한 선수 : n+1명
완주한 선수 : n명

1. 정렬하기

너무 어렵게 생각해서 휘황찬란한 코드가 되어버린 문제.
하지만 단순 for문이나 foreach문을 쓰게 된다면 시간초과로 효율성 검사를 실패하게 된다.
그래서 생각을 하다가 정렬을 해서 값이 다르면 완주하지 못한 선수가 나오겠다는 생각을 했다.
그런데 시간복잡도 생각을 너무 많이 했더니 정렬을 퀵소트로 했다.
퀵소트 평균 Big o가 O(nlogn) 정도이니 빨라질거라 생각을 했는데, 생각해보니 반복하며 배열 값을 비교할 때는 최악의 경우 O(n)의 복잡도가 나오게 된다. 퀵소트를 쓰나 그냥 소트를 쓰나 최종 복잡도 차이는 없었던 것이다.
참고로 퀵소트는 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

2. some 이용해

그리고 some이라는 Javascript Array 내장함수를 사용해 반복문을 돌다가 다른 값이 나오면 그대로 멈추는 코드를 작성했다.
아직 reduce와 같은 자바스크립트 특유의 신기한 내장함수들을 응용하는게 어려워서 활용이 약하다.
다음은 1. 퀵소트, 2. 일반 소트를 사용해 성공한 코드이다.

성공 코드

1. Quick sort 사용 코드

const solution = (participant, completion) => {
    let answer = '';

    quickSort(participant, 0, participant.length - 1);
    quickSort(completion, 0, completion.length - 1);
    let idx = 0;

    completion.some(x => {
        if (x !== participant[idx]) {
            answer = participant[idx];
            return true;
        }
        idx++;
    });

    if (answer === '') answer = participant[participant.length - 1];

    return answer;
}

const quickSort = (array, left, right) => {
    if (left >= right) return;

    let pivot = array[right];
    let l = left;
    let r = right - 1;

    while (l <= r) {    // 교차하기 전까지 진행
        while (l <= r && array[l] <= pivot) l++;
        while (l <= r && array[r] >= pivot) r--;
        if (l < r) swapElement(array, l, r);
    }
    swapElement(array, l, right);
    quickSort(array, left, l - 1);
    quickSort(array, l + 1, right);

}

const swapElement = (array, first, second) => {
    let temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

2. sort 사용 코드

const solution = (participant, completion) => {
    let answer = '';

    participant.sort();
    completion.sort();
    let idx = 0;

    completion.some(x => {
        if (x !== participant[idx]) {
            answer = participant[idx];
            return true;
        }
        idx++;
    });

    if (answer === '') answer = participant[participant.length - 1];

    return answer;
}