문제 개요
서로 다른 숫자들로 이루어진 리스트가 주어졌을 때, 이 리스트를 오름차순으로 정렬하기 위해 필요한 최소 교환(swap) 횟수를 구하는 문제입니다.
예를 들어 입력이 nums = [3, 1, 7, 5]라고 가정해 보겠습니다. 먼저 3과 1을 교환하고, 그다음 5와 7을 교환하면 [1, 3, 5, 7]이 되므로 정답은 2가 됩니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 원본 리스트를 정렬한 결과(sort_seq)를 미리 만들어 두고, 각 위치에 "실제로 있어야 할 값"과 "현재 들어 있는 값"을 비교하며 자리를 바꿔 나가는 방식입니다. 이때 특정 값의 현재 위치를 빠르게 조회하기 위해 딕셔너리(table)에 각 숫자의 인덱스를 저장해 둡니다.
알고리즘의 구체적인 단계는 다음과 같습니다.
sort_seq:= 입력 리스트nums를 정렬한 결과table:= 각 숫자의 현재 인덱스를 저장하는 새로운 맵(딕셔너리)nums의 모든 인덱스 i와 값 n에 대해table[n] = i를 기록swaps = 0으로 초기화- i를 0부터 리스트 길이까지 반복하며:
n := nums[i],s_n := sort_seq[i],s_i := table[s_n]s_n이n과 다르면(자리가 어긋나 있으면) 두 값을 교환하고swaps를 1 증가시킨 뒤,table의 위치 정보도 함께 갱신
- 반복이 끝나면
swaps를 반환
매번 교환이 일어날 때마다 최소 한 개의 요소는 제자리에 확정되므로, 이 탐욕적(greedy) 방식으로 항상 최소 교환 횟수를 얻을 수 있습니다.
예제 코드
class Solution:
def solve(self, nums):
sort_seq = sorted(nums)
table = {}
# 각 숫자의 현재 위치를 딕셔너리에 기록
for i, n in enumerate(nums):
table[n] = i
swaps = 0
for i in range(len(nums)):
n = nums[i] # 현재 위치의 값
s_n = sort_seq[i] # 이 위치에 있어야 할 값
s_i = table[s_n] # 있어야 할 값의 현재 위치
if s_n != n:
swaps += 1
nums[s_i] = n
nums[i] = s_n
table[n] = s_i
table[s_n] = i
return swaps
ob = Solution()
nums = [3, 1, 7, 5]
print(ob.solve(nums))입력
[3, 1, 7, 5]
출력
2
동작 과정 추적
입력 [3, 1, 7, 5]와 정렬된 목표 배열 [1, 3, 5, 7]을 기준으로 실행 흐름을 살펴보겠습니다.
- i = 0: 현재 값 3, 필요한 값 1 → 위치 0과 1을 교환 →
[1, 3, 7, 5], swaps = 1 - i = 1: 현재 값 3, 필요한 값 3 → 이미 올바른 자리, 교환 없음
- i = 2: 현재 값 7, 필요한 값 5 → 위치 2와 3을 교환 →
[1, 3, 5, 7], swaps = 2 - i = 3: 현재 값 7, 필요한 값 7 → 이미 올바른 자리, 교환 없음
최종적으로 반환되는 값은 2로, 예상한 결과와 일치합니다.
시간·공간 복잡도
정렬에 O(n log n)이 소요되고, 이후의 순회와 교환 작업은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 정렬된 사본과 딕셔너리를 추가로 사용하므로 공간 복잡도는 O(n)입니다.