교환(임시)

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

1039번: 교환

문제요약:

정수 n과 k가 주어질 때, n의 자리수 중에서 두개를 임의 로 k번 바꿀 때,나올 수 있는 수의 최댓값을 구하여라. 단 앞자리가 0으로 시작해서는 안된다.

 

난이도:

골드 2

 

소요시간:

1시간 +@

 

제출횟수:

5회 +@

 

코딩:

from collections import deque,defaultdict
n,k = map(int,input().split())

n = list(str(n))
q = deque([(n,0)])    
result = []
once = defaultdict(int)
while q:
    s,t = q.popleft()
    if t==k-1:
        result.append(s)
        continue
    for i in range(len(n)):
        for j in range(i+1,len(n)):
            temp = s[:]
            temp[i],temp[j] = temp[j],temp[i]
            if temp[0] == '0':
                continue
            if not once[tuple(temp+[t])]:
                once[tuple(temp+[t])] +=1
                q.append([temp,t+1])
ans = -1
if result:
    if len(result[0]) == 1:
        print(-1)
    else:
        for s in result:
            for i in range(len(n)):
                for j in range(i+1,len(n)):
                    temp = s[:]
                    temp[i],temp[j] = temp[j],temp[i]
                    if temp[0] == '0':
                        continue
                    if ans<int(''.join(temp)):
                        ans = int(''.join(temp))
        print(ans)
else:
    print(-1)

6개월 전에, 그리디로 시도 했다가 풀지 못했고, 이번엔 시작할때, 그 그리디로 시도했던 예제들이 기억나며 이번에는 BFS로 풀기로 했습니다. (안됐던 예제, 가령 12345, 5 가 있고, 12345, 6 이 있을때 즉 똑같은 숫자인데 k가 달라졌을때 6번 케이스 에서의 5번째가 첫번째 케이스의 답과 다르기 때문에 고려해야 할것이 더 많음)그래서 BFS로 풀고 모든 경우를 다 보는 케이스로 했는데 이때 중복 되는 것들을 처리 해주지 않으면 메모리오류 및 시간초과가 나기 때문에, defaultdict함수를 사용해서 같은 케이스라면 넘어가도록 했습니다.

 

이때 처음안 사실이 원래 중복을 처리할때 set함수를 많이 쓰는데 오류가 나서 확인해보니 , set함수, 그리고 dict함수도 unhashable value 즉 바뀌지 않는 것들만 받을 수 있고, int,str,tuple  가령 바뀔수 있는 list 같은것들은 받을 수 가 없었습니다. 그래서 once라는 defaultdict에 temp를 tuple로 묶어 넣어주었고, 이때 그냥 temp만 넣는게 아니라 남은 숫자도 넣어주었습니다. (위에서 안됐던 예시처럼 123,5 와 123,4 는 다름) 그리고 바꿀때 마다 0이 앞으로 나오는 처리를 따로 해주었고, 맨  마지막에 같은 메커니즘을 돈 후에  최대값을 정해주었습니다.그리고 defaultdict선언시에 뒤에 parameter는 value값의 형태입니다. 안해도 처음 접근할때 할당을 해주는거면 상관이 없는데, 위처럼 +=1 처럼 참조 하려면 다음과같이  int라고 형태를 선언해주어야합니다.

 

마지막으로 이렇게 했을때도 반례들이 있어, 결국 질문계시판에서 반례를 보고 수정했는데, 1 1 , 10 1, 1 10 등이 있습니다.먼저 앞에 가 한자리 수라면 바꿀것이 없기때문에 -1이 나와야하고, 처음엔 ans가 0이었는데 이때 10 1이라면 ans 가 한번도 최신화 되지않기 때문에 시작값을 -1로 하여 새로 할당되지않아도 저렇게 나올 수 있게 바꿔주었습니다.

조금 복잡하게 짠거같아 후에 간단히 수정이 필요해 보입니다.