매우 큰 정수를 나타내는 num이라는 문자열이 있고 또 다른 값 k가 있다고 가정합니다. 최대 k 번 값의 인접한 두 자리를 바꿀 수 있습니다. 얻을 수 있는 최소값을 찾아야 합니다.
따라서 입력이 num ="5432" k =4와 같으면 첫 번째 숫자가 5432이기 때문에 출력은 2453이 됩니다. 그런 다음 첫 번째 단계 후에는 4532, 4523, 4253, 마지막 단계 2453이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
min_num :=num의 자릿수 정렬
-
나는 :=0, to_find :=0
-
num은 min_num과 같지 않고 k> 0 및 i
-
indx :=num의 인덱스 i에서 찾을 항목의 인덱스
-
indx가 -1과 같지 않은 동안 수행
-
indx - i <=k인 경우
-
num :=num[인덱스 0에서 i-1까지] num을 연결[indx] concatenatenum[인덱스 i에서 indx-1로] num을 연결[인덱스 indx+1에서 끝까지]
-
k :=k -(인덱스 - i)
-
나는 :=나는 + 1
-
to_find :=0
-
indx :=num의 인덱스 i에서 찾을 항목의 인덱스
-
-
그렇지 않으면
-
루프에서 나오다
-
-
-
to_find :=to_find + 1
-
-
반환 번호
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
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