파이썬 코딩테스트 강좌, 배열에서 K번째 수 찾기

본 강좌에서는 배열에서 K번째 수를 찾는 문제를 해결하는 방법에 대해 다루겠습니다. 이 문제는 코딩테스트에서 자주 출제되는 유형으로, 효율적인 알고리즘 설계 및 구현 능력을 기를 수 있는 좋은 기회가 될 것입니다.

문제 설명

주어진 정수 배열과 정수 K가 있을 때, 배열을 오름차순으로 정렬한 후, K번째 수를 출력하는 문제입니다. 배열의 인덱스는 0부터 시작합니다. 즉, K=1일 경우 두 번째로 작은 수를 찾아야 합니다.

입력

첫 번째 줄: 정수 N (배열의 크기)
두 번째 줄: N개의 정수로 이루어진 배열
세 번째 줄: 정수 K (찾고자 하는 수의 순위)

출력

K번째 수를 출력합니다.

예제

예제 1

예제 2

입력
6
7 8 9 5 6 3
1

출력
3

문제 분석

이 문제를 해결하기 위해서는 배열을 정렬해야 합니다. 배열을 정렬한 후 K번째 인덱스에 위치한 값을 반환하면 됩니다. 정렬의 시간 복잡도는 배열의 크기 N에 대해 O(N log N)입니다. 이후 K번째 수를 찾는 시간 복잡도는 O(1)로 매우 효율적입니다.

알고리즘 접근

배열을 입력받는다.
배열을 오름차순으로 정렬한다.
K번째 수를 출력한다.

구현

이제 Python 코드를 작성해 보겠습니다. 아래는 이 문제를 해결하는 간단한 코드입니다.

def find_kth_number(arr, k):
    # 배열을 오름차순으로 정렬
    sorted_arr = sorted(arr)
    # K번째 수를 반환 (인덱스가 0부터 시작하므로 k-1)
    return sorted_arr[k - 1]

# 입력 처리
N = int(input())
arr = list(map(int, input().split()))
K = int(input())

# K번째 수 찾기
result = find_kth_number(arr, K)
print(result)

코드 설명

위 코드는 간단하게 함수 find_kth_number를 정의하고, 배열을 받아서 정렬한 후 K번째 수를 반환합니다. 인덱스를 조정하기 위해 k - 1을 사용합니다. 사용자가 입력한 배열 크기, 배열의 요소, K 값을 순차적으로 받아 처리합니다.

성능 분석

이 알고리즘은 O(N log N)의 시간 복잡도를 가지며, 일반적으로 Python의 기본 정렬 알고리즘인 Timsort를 활용하여 최적의 성능을 발휘합니다. 데이터가 크지 않거나 K 값이 작은 경우 매우 빠른 성능을 보여줍니다.

테스트 케이스

제작한 코드는 다양한 테스트 케이스에서 검증될 수 있습니다. 아래는 몇 가지 추가 테스트 케이스입니다.

테스트 케이스 1

입력
7
10 7 8 6 5 4 3
4

출력
6

테스트 케이스 2

입력
8
20 30 10 40 50 5 2 1
3

출력
10

결론

이번 강좌를 통해 배열에서 K번째 수를 찾는 기초적인 문제를 해결하는 방법을 배웠습니다. 이 문제는 코딩테스트에서 자주 등장하며, 정렬의 기본 개념과 Python의 기본 함수 사용법을 익히는 데 매우 유용합니다. 다양한 문제를 풀면서 여러분의 알고리즘 능력을 향상시키세요!