[ Python ] K 번째 수 정렬

[Programmers/Python] K번째수 풀이 정리

문제 링크: Programmers - K번째수

리스트 슬라이싱, 정렬, 인덱싱을 이용해 각 명령마다 원하는 위치의 값을 구하는 문제다.

 이번 문제의 핵심은 commands에 들어 있는 각 명령을 하나씩 처리하는 것이다. 각 명령은 [i, j, k] 형태이며, 배열의 i번째부터 j번째까지 자른 뒤 정렬하고, 그중 k번째 수를 결과 리스트에 담아야 한다.

리스트 슬라이싱 sorted() for문 2차원 리스트 인덱싱 1-based index

1. 문제 핵심

정수 배열 array와 명령 배열 commands가 주어진다. commands의 각 원소는 [i, j, k] 형태이다.

i: 자르기 시작 위치
j: 자르기 끝 위치
k: 정렬한 배열에서 선택할 위치

예를 들어 명령이 [2, 5, 3]이라면 배열의 2번째부터 5번째까지 자르고, 그 구간을 정렬한 뒤, 3번째 값을 선택한다.

문제에서 말하는 i번째, j번째, k번째는 사람이 세는 기준이다. Python 리스트 인덱스는 0부터 시작하므로 시작 위치와 선택 위치를 조정해야 한다.

2. 처음 접근

def solution(array, commands):
    answer = []
    for arr in range(len(commands)):
        a = array[arr[0]:arr[1]]
        answer.append(a.sorted()[arr[2]])
    return answer

처음 접근은 명령을 하나씩 순회하면서 배열을 자르고, 정렬한 뒤 특정 위치의 값을 가져오려는 방향이었다. 전체적인 흐름은 맞았다.

다만 range(len(commands))를 사용하면 arr에는 명령 자체가 아니라 인덱스 숫자가 들어간다. 따라서 arr[0], arr[1], arr[2]처럼 접근할 수 없다.

3. 처음 코드에서 틀린 점

1) arr는 명령이 아니라 인덱스 숫자였다

for arr in range(len(commands))처럼 작성하면 arr에는 0, 1, 2 같은 숫자가 들어간다.

잘못된 흐름: arr = 0, arr = 1, arr = 2
필요한 흐름: arr = [2, 5, 3], arr = [4, 4, 1], arr = [1, 7, 3]

따라서 commands 안의 명령을 직접 하나씩 꺼내야 한다.

for arr in commands:

2) sort()는 정렬된 리스트를 반환하지 않는다

중간에는 다음과 같이 sort() 결과를 바로 사용하려고 했다.

answer.append(a.sort()[arr[2]])

하지만 sort()는 리스트 자체를 정렬할 뿐, 정렬된 리스트를 반환하지 않는다. 반환값은 None이다.

a.sort(): 원본 리스트 a를 직접 정렬, 반환값은 None
sorted(a): 정렬된 새 리스트를 반환

이 문제에서는 정렬된 리스트를 새 변수에 저장해서 사용하는 sorted()가 더 직관적이다.

b = sorted(a)

3) 시작 인덱스와 k번째 위치를 조정해야 한다

문제에서 2번째부터 5번째까지라고 하면 Python에서는 index 1부터 index 4까지를 의미한다.

문제 기준 1번째 원소 → Python index 0
문제 기준 2번째 원소 → Python index 1
문제 기준 3번째 원소 → Python index 2

따라서 시작 위치는 arr[0] - 1로 바꿔야 한다. 반면 슬라이싱의 끝 인덱스는 포함되지 않으므로 arr[1]은 그대로 사용하면 된다.

슬라이싱 시작: arr[0] - 1
슬라이싱 끝: arr[1]
k번째 값 선택: arr[2] - 1

4. 단계별 개선 과정

1) commands의 원소를 직접 순회

for arr in commands:

이렇게 작성하면 arr에는 [i, j, k] 형태의 명령이 하나씩 들어온다.

2) 배열 자르기

a = array[(arr[0] - 1):arr[1]]

arr[0]은 문제 기준 시작 위치이므로 Python 인덱스에 맞춰 1을 빼준다. arr[1]은 슬라이싱 끝 위치로 사용한다.

3) 정렬하기

b = sorted(a)

잘라낸 배열 a를 오름차순으로 정렬한 새 리스트를 b에 저장한다.

4) k번째 값 선택

answer.append(b[arr[2] - 1])

문제에서 말하는 k번째도 1부터 세는 기준이다. Python 인덱스는 0부터 시작하므로 arr[2] - 1을 사용한다.

5. 최종 풀이

def solution(array, commands):
    answer = []
    for arr in commands:
        a = array[(arr[0] - 1):arr[1]]
        b = sorted(a)
        answer.append(b[arr[2] - 1])
    return answer

 각 명령을 하나씩 꺼내고, 해당 구간을 자른 뒤 정렬한다. 이후 정렬된 리스트에서 k번째 값을 Python 인덱스에 맞게 선택하여 answer에 추가한다.

for arr in commands: 명령 하나씩 꺼내기
array[(arr[0] - 1):arr[1]]: i번째부터 j번째까지 자르기
sorted(a): 자른 배열 정렬하기
b[arr[2] - 1]: k번째 값 선택하기

6. 풀이 흐름

예를 들어 다음과 같은 입력이 있다고 하자.

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

명령 [2, 5, 3]의 의미는 2번째부터 5번째까지 자르고, 정렬한 뒤, 3번째 값을 선택하는 것이다.

자르기: array[1:5] → [5, 2, 6, 3]
정렬하기: [2, 3, 5, 6]
3번째 값 선택: 5

여기서 array[1:5]는 index 1부터 index 4까지 가져온다. 슬라이싱의 끝 인덱스는 포함되지 않기 때문에 문제에서 말하는 2번째부터 5번째까지와 정확히 대응된다.

문제의 위치 표현은 1부터 시작하고, Python 인덱스는 0부터 시작한다. 이 차이를 정확히 맞추는 것이 이 문제의 핵심이다.

7. 유사 유형 풀이

같은 핵심 문법인 리스트 슬라이싱, 정렬, 특정 위치 값 선택을 사용하는 유사 문제를 풀었다.

정수 배열 array와 명령 배열 commands가 주어진다. 각 명령은 [i, j] 형태이며, 배열의 i번째부터 j번째까지 자른 뒤 정렬했을 때 두 번째로 큰 수를 구한다.

def solution(array, commands):
    answer = []
    for arr in commands:
        a = array[(arr[0] - 1):arr[1]]
        b = sorted(a)
        answer.append(b[-2]) 
    return answer

원래 문제와 같은 점

 두 문제 모두 명령에 따라 배열의 일부 구간을 자르고, 그 구간을 정렬한 뒤, 특정 위치의 값을 선택한다.

원래 문제: answer.append(b[arr[2] - 1])
유사 문제: answer.append(b[-2])

핵심 구조: 자르기 → 정렬하기 → 원하는 위치 선택하기

원래 문제와 다른 점

 원래 문제는 명령 안에 k가 주어지므로 arr[2] - 1 위치의 값을 선택한다. 유사 문제는 항상 두 번째로 큰 수를 구하므로 정렬된 리스트의 뒤에서 두 번째 값인 b[-2]를 선택한다.

원래 문제: [i, j, k]에서 k번째 값 선택
유사 문제: [i, j]에서 항상 두 번째로 큰 값 선택

8. 핵심 정리

이번 유형의 핵심은 문제의 1-based index를 Python의 0-based index로 바꾸고, 슬라이싱과 정렬을 순서대로 적용하는 것이다.

 명령 [i, j, k]가 주어졌을 때, Python에서는 array[i - 1:j]로 구간을 자른다. 시작 위치는 1을 빼고, 끝 위치는 그대로 둔다. 그다음 sorted()로 정렬된 새 리스트를 만든 뒤, k번째 값은 k - 1 인덱스로 선택한다.

구간 자르기: array[i - 1:j]
정렬하기: sorted(구간)
k번째 값 선택: 정렬결과[k - 1]

9. 사용한 핵심 문법 정리

for문으로 리스트 순회

for arr in commands처럼 작성하면 commands 안의 명령을 하나씩 직접 꺼낼 수 있다.

2차원 리스트 인덱싱

arr[0], arr[1], arr[2]처럼 명령 리스트 안의 값을 각각 꺼낼 수 있다.

리스트 슬라이싱

array[start:end]는 start부터 end - 1까지의 값을 잘라 새 리스트로 반환한다.

1-based index 보정

문제에서 말하는 i번째, k번째는 1부터 시작하므로 Python 인덱스에 맞게 i - 1, k - 1로 바꿔야 한다.

sorted()

sorted(a)는 리스트 a를 정렬한 새 리스트를 반환한다.

sort()

a.sort()는 리스트 a 자체를 정렬하지만 반환값은 None이다. 따라서 바로 인덱싱할 수 없다.

음수 인덱싱

b[-1]은 마지막 값, b[-2]는 뒤에서 두 번째 값을 의미한다. 유사 문제에서 두 번째로 큰 수를 고를 때 사용했다.

append()

answer.append(value)는 결과 리스트에 값을 하나씩 추가한다.

10. 기본 Python 구조

for command in commands:
    sliced = array[command[0] - 1:command[1]]
    sorted_list = sorted(sliced)
    answer.append(sorted_list[command[2] - 1])

정리하면, 이번 문제는 슬라이싱 범위와 인덱스 기준을 정확히 맞추는 문제다. array[i - 1:j]로 구간을 자르고, sorted()로 정렬한 뒤, k - 1 위치의 값을 선택하면 된다.