09/02 교환 BOJ 1039 파이썬

 

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

1039번: 교환

1. 풀이 : 1774ms

BOJ 1039 교환 파이썬

BFS 문제

맨 처음에 모든 자릿수에 대해 방문여부를 확인 하는 배열을 만들려고 했지만 자꾸 시간초과가 났다.

전체 숫자 범위(1에서 1,000,000)와 모든 깊이 범위에 대해 방문 여부를 나타내는 배열을 만든뒤 BFS를 수행한다.

 

N, K = input().split()
M = len(N) #전체 자릿수
K = int(K)
#전체 숫자 범위와 모든 깊이 범위에 대해 방문 여부를 나타내는 배열
cache =[[False for i in range(11)] for i in range(1000001)]
#BFS 큐
q=[]
q.append([[ch for ch in N],0]) # 시작 숫자와 깊이를 넣어준다.
cache[int(N)][0]=True

def swap(N, idx1, idx2):
	'''
    자리 두개를 바꿔주는 함수
    '''
    temp = N[idx1]
    N[idx1] = N[idx2]
    N[idx2] = temp

answer = -1
while q:
    n, depth = q.pop(0)

    if depth == K: #깊이가 K면 비교해서 최대값
        answer = max(answer, int(''.join(n)))
        continue
       
    #M 자리에서 두자리를 선택한다.
    for i in range(M): 
        for j in range(i+1,M):
            if i ==0 and n[j] =='0': 
            # 바꾸는 인덱스가 맨 앞이고 바꿔야되는 값이 '0'이면 바꾸지 않는다.
            # 첫째자리가 0이 되기 때문에
                continue

            swap(n, i, j) #자리를 바꾸고
            n_int = int(''.join(n)) #정수형으로 바꾼뒤
            if not cache[n_int][depth+1]: #해당 값과 깊이를 방문하지 않았으면
                cache[n_int][depth+1] = True #방문하고
                q.append([n.copy(), depth+1]) # q에 집어넣어준다.
            swap(n, i, j) # 자리를 다시 바꿔준다.

print(answer)

2. 다른 풀이 :  56ms

import sys

arr = list(sys.stdin.readline().split())
N = arr[0]
K = int(arr[1])
M = len(N)
if M < 2: #자리수가 1개면 -1을 출력하고 종료
    print(-1)
    sys.exit()

N = list(map(int,N)) 
N1 = list(map(int,N)) # 최대값을 만들기 위한 리스트
N1.sort(reverse=True) # 최대값

result =[]

def change_index(arr,a,b):
	'''
    자리를 바꾸는 함수
    '''
    temp = arr[b]
    arr[b] = arr[a]
    arr[a] = temp
    return arr

def arrToNum(arr):
	'''
    배열을 숫자로 돌려주는 함수
    '''
    arr.reverse()
    result = 0
    n = 0
    for i in arr:
        result += i*(10**n)
        n+=1
    return result
    
def change_dfs(depth, arr):
    if depth == K: #깊이가 K가 되면
        result.append(arrToNum(arr)) #arr를 정수로 바꿔서 결과에 넣어준다.
        return
        
    a = -1
    for i in range(M): #전체 자리에 대해
        if arr[i] != N1[i]: #최대값이 아닌 지점에 대해
            a = i #값을 기록하고
            break #멈춘다.
            
    if a == -1: #전부 최대값과 동일하면
        if M != len(set(arr)): #중복을 제거한 값과 전체 자릿수가 다르면
            print(arrTonum(arr)) # 그 값을 출력하고 종료
            sys.exit()
            
        else:
            arr = change_index(arr,M-1,M-2) #맨끝자리(M-1)와 그 다음 자리(M-2)를 바꾼다,
            
            if arr[0] == 0: #바꾸다가 첫째자리가 0이되면 종료
                print(-1)
                sys.exit()
                
            else:
                change_dfs(depth+1,arr)
                return
                
    b_index = []
    
    for i in range(a+1,M):
        if N1[a] == arr[i]: #최대값과 같은 자릿수를
            b_index.append(i) #b_index에 넣어준다.
            
    for i in b_index:
        arr1 = list(map(int,arr))
        change_dfs(depth+1, change_index(arr1,a,i))








change_dfs(0,N)

result_max = 0
for i in result:
    if i > result_max:
        result_max = i
print(result_max)