매우 큰 정수를 나타내는 문자열 num과 정수 k가 주어진다고 가정해 봅시다. 우리는 인접한 두 자릿수를 서로 교환(swap)할 수 있으며, 이러한 교환은 최대 k번까지만 허용됩니다. 이때 만들 수 있는 가장 작은 정수를 구하는 것이 목표입니다.
예를 들어 num = "5432", k = 4가 입력으로 주어지면 결과는 2453이 됩니다. 과정을 살펴보면 처음 숫자는 5432이고, 첫 번째 교환 후 4532, 다음 4523, 그다음 4253, 마지막 교환 후 2453이 됩니다.
문제 해결 접근 방법
이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 앞쪽 위치부터 차례대로 해당 자리에 놓을 수 있는 가장 작은 숫자를 찾아, 필요한 교환 횟수가 남은 k 이하일 때 앞으로 끌어오는 방식입니다.
구체적인 단계는 다음과 같습니다.
min_num := num의 자릿수들을 오름차순으로 정렬한 값
i := 0, to_find := 0 으로 초기화
num이 min_num과 같지 않고, k > 0이며, i가 num의 길이보다 작은 동안 반복:
indx := 인덱스 i부터 탐색했을 때 to_find가 처음 나타나는 위치
indx가 -1이 아닌 동안 반복:
만약 indx - i <= k라면:
num := num[0:i] + num[indx] + num[i:indx] + num[indx+1:] 로 재구성 (to_find를 i번째 자리로 이동)
k := k - (indx - i)
i := i + 1
to_find := 0 으로 초기화 후 indx를 다시 탐색
그렇지 않으면(교환 횟수가 부족하면):
내부 루프를 빠져나감
to_find := to_find + 1 (찾을 숫자를 하나 증가)
최종적으로 num을 반환
예제 코드
아래의 Python 구현을 통해 더 잘 이해해 보겠습니다.
def solve(num, k): min_num = sorted(list(num)) min_num = ''.join(min_num) i = 0 to_find = 0 while num != min_num and k > 0 and i < len(num): indx = num.find(str(to_find), i) while indx != -1: if indx - i <= k: num = num[:i] + num[indx] + num[i:indx] + num[indx+1:] k -= (indx - i) i += 1 to_find = 0 indx = num.find(str(to_find), i) else: break to_find += 1 return num num = "5432" k = 4 print(solve(num, k))
입력
"5432", 4
출력
2453
이 알고리즘은 각 자리마다 남은 교환 횟수 안에서 가져올 수 있는 최소 숫자를 우선 배치하므로, 주어진 조건 내에서 항상 사전순으로 가장 작은 결과를 보장합니다.