연습

K번째수

프로그래머스 42748

갱신: 2026-10-02

문제 보기 · Level 1 · 고득점 Kit · 정렬 · 정답률 74% · 푼 사람 117,064명 (2026-09-30 기준)¹

문제

명령 [i, j, k]마다 array의 i번째부터 j번째까지 잘라 정렬한 뒤 k번째 수를 구한다. 모든 명령의 결과를 배열로 돌려준다. 번호는 1부터 센다.

array 길이 1~100, 원소 1~100
commands 길이 1~50

풀이

막히면 한 단계씩 펼친다.

필요한 개념

리스트와 문자열: 자르기(슬라이싱)와 번호가 0부터라는 점
정렬과 정렬 기준: sorted

1단계 · 작은 예로 손으로 풀기

array = [9, 4, 7, 1], 명령 [1, 3, 2]

1번째부터 3번째까지 자른다 → [9, 4, 7]
정렬한다 → [4, 7, 9]
2번째 수 → 7

정렬해서 k번째 값을 꺼내는 것은 기술통계에서 중앙값과 분위수를 구하는 방법과 같다. 값이 10개면 90% 분위수(최근접 순위 방식)는 정렬한 뒤 9번째 값이다.

2단계 · 가장 단순한 방법과 그 속도

명령마다 문제에 적힌 대로 자르고 정렬한다. 한 명령에 최대 100개를 정렬하니 약 100 × 7 = 700번 비교, 명령 50개면 35,000번이다. 7은 100개를 거듭 반으로 나눠 한 개씩이 될 때까지 나누는 횟수로, \(\lg 100 \approx 6.64\)를 올린 값이다(로그). 아주 넉넉하다. 이 문제는 단순한 방법이 곧 답이다.

3단계 · 핵심 아이디어

어려운 점은 번호 옮기기 하나다. 문제는 1부터 세고 파이썬은 0부터 센다.

1부터 센 “i번째부터 j번째까지”는 파이썬 번호로 i − 1부터 j − 1까지다. 자르기는 끝 번호를 빼므로 array[i - 1:j]다.
1부터 센 “k번째”는 part[k - 1]이다.

4단계 · 코드 흐름

답을 모을 빈 리스트를 만든다.
명령마다 i, j, k를 꺼낸다.
array[i - 1:j]를 잘라 정렬한다.
정렬한 리스트의 k - 1번 칸을 답에 넣는다.
답 리스트를 돌려준다.

5단계 · 파이썬 코드

def solution(array, commands):
    answer = []
    for i, j, k in commands:            # [2, 5, 3]이면 i=2, j=5, k=3
        part = sorted(array[i - 1:j])   # 잘라서 정렬한 새 리스트
        answer.append(part[k - 1])
    return answer

for i, j, k in commands: 명령 하나가 세 칸짜리 리스트라서, 꺼내자마자 세 이름에 나눠 담는다.
sorted(...): 정렬한 새 리스트를 돌려준다. array는 그대로라서 다음 명령에 영향이 없다.

6단계 · 실행 추적

array = [1, 5, 2, 6, 3, 7, 4]

명령	자른 부분 `array[i-1:j]`	정렬	k번째
[2, 5, 3]	[5, 2, 6, 3]	[2, 3, 5, 6]	5
[4, 4, 1]	[6]	[6]	6
[1, 7, 3]	[1, 5, 2, 6, 3, 7, 4]	[1, 2, 3, 4, 5, 6, 7]	3

답은 [5, 6, 3]이다.

7단계 · 복잡도와 흔한 실수

명령 m개, 배열 길이 n이면 \(O(m \cdot n \log n)\)이다.

array[i:j]라고 쓰면 한 칸씩 밀린다.
array.sort()로 원래 배열을 정렬해 버리면 다음 명령이 바뀐 배열을 자르게 된다. 잘라 낸 복사본만 정렬한다.

검증: 문제의 예시를 통과했고, 무작위 입력 1,000개에서 “정렬하지 않고 k번째로 작은 값을 직접 세는” 다른 풀이와 결과가 같았다 — 05_pg42748_p1.py

프로그래머스 스쿨, “K번째수” (https://school.programmers.co.kr/learn/courses/30/lessons/42748), 2026-09-30 조회. ↩