자바스크립트 코딩테스트 강좌, 배열에서 K번째 수 찾기

코딩테스트는 현대 소프트웨어 개발에서 매우 중요한 요소입니다. 기업들은 개발자의 문제 해결 능력을 평가하기 위해 다양한 알고리즘 문제를 출제합니다. 오늘은 배열에서 K번째 수를 찾는 문제를 다루어 보겠습니다. 이 문제는 배열을 다루는 기본적인 알고리즘 기술을 쌓을 수 있는 좋은 예시입니다.

문제 설명

주어진 배열 arr와 정수 k가 있을 때, arr에서 K번째로 작은 수를 찾아 반환하시오. 배열의 인덱스는 0부터 시작합니다.

입력

• 정수 배열 arr, 길이는 1 이상 100,000 이하.
• 정수 k, 1 이상 배열의 길이 이하.

출력

arr에서 K번째로 작은 수를 반환한다.

예시

풀이 과정

이 문제는 배열을 정렬한 후에 K번째 요소를 쉽게 찾을 수 있으나, 정렬 방법에 따라 시간 복잡도가 달라질 수 있습니다. 여기서는 두 가지 접근 방식을 살펴보겠습니다.

해결 방법 1: 배열 정렬 후 K번째 수 찾기

1. 배열을 오름차순으로 정렬합니다.
2. K번째 수를 찾기 위해 인덱스 k - 1에 해당하는 값을 반환합니다.

자바스크립트 코드 예시

function findKthNumber(arr, k) {
    arr.sort((a, b) => a - b); // 배열을 오름차순으로 정렬
    return arr[k - 1]; // K번째 수 반환
}

// 예시 실행
console.log(findKthNumber([3, 1, 2, 4, 5], 2)); // 2
console.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); // 7

위 코드에서는 단순히 배열을 정렬하고 K번째 요소를 찾았습니다. 이 방법의 시간 복잡도는 O(n log n)입니다. 하지만, 반드시 정렬할 필요 없이 K번째 작은 수만 찾는 방법이 있습니다.

해결 방법 2: Quickselect 알고리즘

Quickselect 알고리즘은 퀵소트와 유사한 방식으로 K번째 작은 수를 찾는 방법입니다. 이 방법은 평균적으로 O(n)의 시간 복잡도를 가집니다. 이 알고리즘은 부분 배열을 설정하고, 피벗을 선택하는 방식으로 진행됩니다.

1. 배열에서 피벗 요소를 선택합니다.
2. 피벗보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치시킵니다.
3. 피벗의 위치가 K번째 수의 위치와 같으면 피벗을 반환합니다.
4. 그렇지 않으면, K번째 수가 좌측 또는 우측 부분 배열에 있는지에 따라 적절한 부분 배열에서 재귀적으로 Quickselect를 수행합니다.

자바스크립트 코드 예시

function quickSelect(arr, left, right, k) {
    if (left === right) {
        return arr[left]; // 배열에 자신만 있는 경우
    }
    const pivotIndex = partition(arr, left, right);
    if (k === pivotIndex) {
        return arr[k]; // K번째 수 발견
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

function partition(arr, left, right) {
    const pivot = arr[right]; // 마지막 요소를 피벗으로 선택
    let i = left; 
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // 교환
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]]; // 피벗 최종 위치
    return i; // 피벗의 인덱스 반환
}

function findKthNumber(arr, k) {
    return quickSelect(arr, 0, arr.length - 1, k - 1); // K-1을 인자로 전달
}

// 예시 실행
console.log(findKthNumber([3, 1, 2, 4, 5], 2)); // 2
console.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); // 7

위 코드를 통해 Quickselect 알고리즘을 이용하여 K번째 수를 효율적으로 찾을 수 있습니다. 이 방법은 평균적으로 O(n)의 시간 복잡도를 가지므로 대규모 데이터에서 더욱 유용합니다.

결론

이번 강좌에서는 자바스크립트 코딩테스트에서 자주 다루어지는 배열에서 K번째 수 찾기 문제를 알아보았습니다. 간단한 정렬을 통해서도 문제를 해결할 수 있지만, Quickselect와 같은 효율적인 방법을 사용하여 성능을 극대화할 수 있습니다. 이러한 내용들은 실제 코딩테스트에서 매우 유용하게 활용될 수 있으므로, 꼭 연습해보시기를 권장합니다.

모든 알고리즘은 기본적인 이해가 선행된 후, 다양한 문제를 통해 응용력을 키워가는 것이 중요합니다. 다음 강좌에서는 더 다양한 배열 문제와 고급 알고리즘을 다루어 보겠습니다. 감사합니다!