[프로그래머스]K번째 수

[58] K번째 수

책 구매하기

문제 정보

• 분류: 정렬
• 정답률: 69%
• 권장 시간 복잡도: O(C * K log K)
• 핵심 키워드: 슬라이싱, 정렬, 부분 배열, 인덱스
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748

문제를 읽을 때 체크할 포인트

명령 하나마다 부분 배열을 잘라 정렬하고 k번째 원소를 꺼내면 되는 문제다. 구현 자체는 간단하지만 인덱스가 1 기반이라는 점만 조심하면 된다.

정렬 문제는 손이 바빠지기 전에 비교 기준부터 정리하는 게 먼저다. 어떤 값을 기준으로 한 번만 정렬하면 그다음 오히려 짧아지는 경우가 많다.

풀이 흐름

1. commands를 순회한다.
2. i~j 구간을 잘라 정렬한다.
3. k번째 값을 answer에 넣는다.

구현할 때 놓치기 쉬운 부분

배열을 잘라 정렬한 뒤 k-1번째를 꺼내야 한다. 문제는 1번째, 2번째처럼 사람 기준으로 말하지만 파이썬 인덱스는 0부터 시작한다는 점을 계속 의식해야 한다.

파이썬 정답 코드

def solution(array, commands):
  # commands를 순회한다.
  answer = []
  # i~j 구간을 잘라 정렬한다.
  for i, j, k in commands:
    # k번째 값을 answer에 넣는다.
    answer.append(sorted(array[i - 1:j])[k - 1])
  return answer

시간 복잡도

C는 명령 수, K는 각 명령에서 잘라낸 부분 배열 길이의 최댓값이다.

명령이 C개 있고, 명령 하나를 처리할 때 잘라낸 부분 배열 길이가 최대 K이다. 매 명령마다 그 부분 배열을 정렬하므로 K log K 비용이 C번 반복된다.

따라서 시간 복잡도는 O(C * K log K)이다.