백준 1039 교환 Python 3

https://www.acmicpc.net/problem/1039

1039번: 교환

 

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1039.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque
def make_num():
    q = deque([[str(N), K]])
    visit = [[0]*1000001 for _ in range(K)]
    answer = -1
    while q:
        str_n, cnt = q.popleft()
        if cnt == 0:
            if answer < int(str_n): answer = int(str_n)
            continue
        for i in range(len(str_n)-1):
            for j in range(i+1, len(str_n)):
                if i == 0 and str_n[j] == '0': continue
                new_n = str_n[:i] + str_n[j] + str_n[i+1:j] + str_n[i] + str_n[j+1:]
                if not visit[cnt-1][int(new_n)]:
                    q.append([new_n, cnt-1])
                    visit[cnt-1][int(new_n)] = 1
    return answer

input = sys.stdin.readline
N, K = map(int, input().split())
print(make_num())

---

풀이 과정

풀이 시간 40분

import sys
from collections import deque
def make_num():
	#[문자열로 바꾼 N, 남은 횟수]
    q = deque([[str(N), K]])
    
    #visit[k][n] = 1 -> k번 숫자를 바꾸어 n이 만들어진 경우를 방문 처리
    visit = [[0]*1000001 for _ in range(K)]
    
    answer = -1
    
    while q:
        str_n, cnt = q.popleft()
        
        #K번 숫자를 바꾼 경우,
        if cnt == 0:
        	현재 숫자 n이 answer보다 큰 경우, answer을 갱신한다
            if answer < int(str_n): answer = int(str_n)
            continue
            
        #숫자 바꾸기 i < j
        for i in range(len(str_n)-1):
            for j in range(i+1, len(str_n)):
            	#i가 0번째 자릿수이면서 j번째 숫자가 0인 경우는 바꾸지 않는다
                if i == 0 and str_n[j] == '0': continue
                
                #i번째 숫자와 j번째 숫자를 바꾼 숫자 new_n
                new_n = str_n[:i] + str_n[j] + str_n[i+1:j] + str_n[i] + str_n[j+1:]
                if not visit[cnt-1][int(new_n)]:
                    q.append([new_n, cnt-1])
                    visit[cnt-1][int(new_n)] = 1
                    
    return answer

input = sys.stdin.readline
N, K = map(int, input().split())
print(make_num())

#시간복잡도 = O(V+E), 시간복잡도 = O(n)