- K번 할 수 없는 경우는?
- M이 1이하인 경우
- M에서 0인 자리수를 전부 뺐을 떄 1이하
- 라고 생각했는데, 사실 9000이면 0끼리 교환하면 되니까 틀린 조건. 2자리일 때 일의자리가 0인 경우이다.
- BFS와 DFS의 핵심은 수형도에 있다.
정답풀이
#2022.06.08.00:01 - 00:43
from collections import deque
import sys
input = sys.stdin.readline
def main ():
n,k = map(int,input().split())
m = len(str(n))
if m == 1 :
print(-1)
return
if m==2 and n%10 ==0:
print(-1)
return
def swap(cur, i,j):
# 12345 1,3 -> 14325
curStr = str(cur)
return int(curStr[:i]+curStr[j]+curStr[i+1:j]+curStr[i]+curStr[j+1:])
# BFS
cur_k = 0
q= deque()
q.append(n)
while(q and cur_k<k):
v= set()
for _ in range(len(q)):
cur = q.popleft()
# print('cur:',cur)
for i in range(len(str(cur))):
for j in range(i+1,len(str(cur))):
res = swap(cur,i,j)
if res not in v:
v.add(res)
q.append(res)
# print(cur_k, v,q)
if cur_k == k-1:
print(max(v))
cur_k+=1
return
main()