[ 백준 ][ 골드3 ] 1039번 - 교환 ( 파이썬 )

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

1039번: 교환

 

문제

---

 

코드

---

n, k = map(int, input().split())
n_len = len(str(n))

s1, s2 = set(), set()
s1.add(n)

for _ in range(k):
    while s1:
        x = str(s1.pop())
        for i in range(n_len-1):
            for j in range(i+1, n_len):
                if x[j] == '0' and i == 0:
                    continue
                y = x[:i] + x[j] + x[i+1:j] + x[i] + x[j+1:]
                s2.add(int(y))
    s2, s1 = s1, s2

s1 = list(s1)
s1.sort()
if len(s1) > 0:
    print(s1[-1])
else:
    print(-1)

 

풀이

---

처음엔 그리디로 해결하려 했으나 따져야 할 조건이 너무 많아서 실패했다.

가장 큰 수로만 만들면 되기 때문에 맨 앞부터 큰수랑 위치를 바꿔주고 k가 m보다 길경우, 작을경우, 같은숫자가 여러개 있을 경우 등등 여러가지 경우를 고려해서 만들었지만 그 많은 조건들을 결국 모두 만족시키지 못했고 실패했다.

 

그래서 결국 많은 사람들이 선택한 방법은 '브루트포스'이다.

많은 사람들은 bfs로 방문처리를 통해 메모리를 아낀 풀이를 했지만 여기서는 set으로 간단하게 메모리를 아꼈다.

 

| BruteForce |

1. s1, s2 셋을 만든다.
2. k번 돌면서 s1에 있는 값들을 크기 조건을 따지지 않고 한 번씩 바꿔주고 s2에 저장한다.
3. 1번씩 모두 바꾸고 나면 s2와 s1을 바꾸고 다시 그 s1으로 반복문을 돌린다.
4. 바꿀때 유일한 조건은 0번째 자리에 0이 오면 안된다는 것이다.
5. k번 모두 마치고 s1에 값이 있다면 교환이 이루어진것이고 값이 없다면 교환이 이루어지지 못한 것이다.
6. 교환이 이루어졌다면 가장 큰 값을, 이루어지지 못했다면 -1을 출력한다.