스위프트 코딩테스트 강좌, 배열에서 K번째 수 찾기

코딩 테스트에서의 알고리즘 문제는 실제 업무에서도 자주 사용되는 이론과 실질적인 문제 해결 능력을 평가합니다. 이번 글에서는 배열에서 K번째 수를 찾는 문제를 다뤄보도록 하겠습니다. 이 문제는 배열의 정렬 및 특정 인덱스의 값을 추출하는 기술을 요구합니다.

문제 설명

주어진 정수 배열 array와 정수 k가 주어졌을 때, array를 오름차순으로 정렬한 후 K번째 수를 반환하는 함수를 작성하시오. K번째 수는 1-based indexing입니다.

입력

array: 정수가 포함된 배열, 예: [3, 1, 2, 4, 5]
k: 배열에서의 K번째 수를 찾기 위한 양의 정수

출력

array를 정렬한 후 K번째 수를 출력합니다. 만약 K가 배열의 길이보다 크면 -1을 반환합니다.

예시

입력:
    array = [3, 5, 2, 1, 4]
    k = 3

    출력:
    3

문제 풀이

이 문제의 해결을 위해서는 이와 같은 단계로 진행할 수 있습니다:

입력으로 주어진 배열을 정렬한다.
정렬된 배열에서 K번째 수를 참조하여 반환한다.

단계별 풀이

1단계: 배열 정렬하기

배열을 정렬하는 방법으로는 여러 가지가 있습니다. 일반적으로 사용하는 정렬 알고리즘으로는 퀵 정렬, 병합 정렬, 삽입 정렬 등이 있습니다. 그러나 Swift에서 제공하는 내장 정렬 함수를 사용하면 간편하게 정렬할 수 있습니다.

2단계: K번째 수 찾기

정렬된 배열에서 K번째 수를 찾기 위해서는 K-1 인덱스를 참조하여 해당 값을 반환합니다. 만약 K가 배열의 길이를 초과한다면 -1을 반환해야 합니다.

Swift 코드 구현

func findKthNumber(array: [Int], k: Int) -> Int {
        let sortedArray = array.sorted()
        guard k > 0 && k <= sortedArray.count else {
            return -1
        }
        return sortedArray[k - 1]
    }

// 테스트
let array = [3, 5, 2, 1, 4]
let k = 3
print(findKthNumber(array: array, k: k)) // 출력: 3

복잡도 분석

시간 복잡도: 정렬을 수행하는 시간 복잡도는 O(n log n)입니다. 여기서 n은 배열의 길이입니다.

공간 복잡도: 정렬을 위한 추가 공간 복잡도는 O(n)입니다.

정리

이번 문제를 통해 배열의 정렬과 특정 인덱스 접근 방법에 대해 배웠습니다. 이를 바탕으로 다른 알고리즘 문제에도 적용할 수 있는 기초적인 사고 방식을 키울 수 있습니다.

더 많은 문제풀이와 알고리즘 강좌를 원하신다면 블로그를 지속적으로 방문해 주세요. 감사합니다!