99클럽 코테 스터디_4기 25일차 TIL

TODAY TIL

🔍 문제 소개

이번 포스팅에서는 배열에서 K번째 수를 찾는 문제를 다룹니다. 이 문제는 정렬 알고리즘의 기초를 연습하기에 적합하며, 간단한 구현으로도 해결할 수 있는 문제입니다. 문제를 이해하고, 순서대로 해결 방법과 코드를 공유하겠습니다!

 

📝 문제 설명

문제

• 크기가 N인 배열 A가 주어집니다.
• 배열 A를 오름차순으로 정렬했을 때, 앞에서부터 K번째 수를 출력하세요.

입력 조건

1. 첫 번째 줄: 정수 N과 K
   • 1 ≤ N ≤ 5,000,000, 1 ≤ K ≤ N
2. 두 번째 줄: 배열 A의 원소들
   • -10⁹ ≤ Aᵢ ≤ 10⁹

출력 조건

• 배열을 정렬했을 때 앞에서부터 K번째 수를 출력합니다.

💡 풀이 방법

이 문제는 크게 3단계로 해결할 수 있습니다:

1. 배열 입력받기
2. 오름차순 정렬하기
3. K번째 수 추출하기

🛠️ 코드 구현

Python을 사용하여 문제를 해결하는 코드는 다음과 같습니다:

# 입력 받기
import sys
input = sys.stdin.read
data = input().split()

# N: 배열의 길이, K: 찾고자 하는 위치
N, K = int(data[0]), int(data[1])
A = list(map(int, data[2:]))

# 배열을 정렬
A.sort()

# K번째 수 출력 (1-based index이므로 K-1 사용)
print(A[K - 1])

 

🔎 코드 설명

1️⃣ 입력 받기

• Python의 sys.stdin.read를 사용해 입력 데이터를 한 번에 받습니다.
• 첫 번째 줄에서 N(배열 길이)과 K(찾고자 하는 위치)를 가져옵니다.
• 두 번째 줄에서 배열 A를 리스트로 변환합니다.

2️⃣ 배열 정렬

• 배열 A를 sort() 메서드를 사용해 오름차순 정렬합니다.
  Python의 sort()는 Timsort 알고리즘을 기반으로 작동하며, 시간 복잡도는 **O(N log N)**입니다.

3️⃣ K번째 수 추출

• 배열은 0부터 시작하는 0-based index입니다. 따라서 K번째 수를 찾으려면 A[K-1]을 사용합니다.

🧩 예제 풀이

예제 입력

5 2
4 1 3 2 5

 

풀이 과정

1. 배열의 길이 N = 5, K번째 위치 K = 2
   배열 A = [4, 1, 3, 2, 5]
2. 배열 정렬:

A.sort() → [1, 2, 3, 4, 5]

 

3. K번째 수 추출:

A[K-1] = A[1] = 2

 

4. 출력 결과:

2

 

⏱️ 시간 복잡도 분석

1. 배열 정렬: 정렬의 시간 복잡도는 O(N log N)
2. K번째 수 추출: 상수 시간 O(1)

따라서 전체 시간 복잡도는 **O(N log N)**입니다.

---

📌 추가 팁: 더 효율적인 방법은 없을까?

만약 배열이 매우 커서 메모리나 시간 효율이 중요하다면, Quickselect 알고리즘을 사용해 K번째 수를 찾을 수 있습니다. Quickselect는 평균적으로 **O(N)**의 시간 복잡도로 실행됩니다. 그러나 이 문제에서는 Python의 내장 정렬을 사용하는 것이 가장 간단하고 안정적인 방법입니다.

---

✅ 마무리

배열에서 K번째 수를 찾는 문제는 정렬 알고리즘과 리스트 활용법을 연습할 수 있는 좋은 문제입니다. 이번 포스팅에서는 Python의 기본 정렬 메서드인 sort()를 사용하여 문제를 간단히 해결했지만, 다른 알고리즘을 적용해보는 것도 추천합니다!