[BOJ][Python] 백준 1039번: 교환

1일 1PS 64일차!

📚 문제

---

골드 2 교환

💡 풀이 과정

---

• 처음에는 정렬 과정 중 k 번째로 생각했습니다.
  • 여기에서는 정렬 이후에 남는 횟수에 대해서 처리가 필요합니다.
  • 예를 들어 1234 로 주어지면 maxheap 과 find 등을 통해 교환해 나갈 수 있습니다.
  • 이후 4321 이 되고 나서 교환 횟수가 남았다면 4312, 4321 을 반복해야합니다.
• 하지만 N 은 6 자리 자연수이며 K 는 10 보다 작기 때문에 모든 경우에 대해서 생각했습니다.
  • 전 문제와 연결하기 위해 DFS 를 진행하였습니다.

📌포인트

---

• List
  • python 에서 string 은 불변 객체입니다.
  • swap 을 쉽게 하기 위해서 List(N) 을 진행해 swap 합니다.
• M - N.count(‘0’)
  • N 은 문자열이므로 0 이 아닌 “0” 을 찾아야함에 주의합니다.
  • N = 50, N = 100 같은 경우 변경이 불가능하다 생각했지만 100 은 0과 0 을 교환할 수 있으니 M <= 2 를 추가 조건으로 주어야합니다.
• visited
  • N = 100,000 K = 10
  • 해당 예제에서는 과도한 시간이 발생합니다. 반복되는 작업을 줄이기 위해 visited 를 생성합니다.
  • (N, K) 라 할 때, (321, 2) 와 (321, 3) 는 다른 결과를 나타냅니다.
  • 따라서 가장 간단하게 (N, K) 를 Set 으로 넣어 visited 를 생성해 visited 에 존재하지 않는 경우에만 DFS 를 진행합니다.

💻 코드

---

N, K = input().split()
N = list(N)
M = len(N)
K = int(K)

max_num = -1
visited = set()
visited.add(("".join(N), K  + 1))

def dfs(c):
    global max_num, visited

    if c == 0:
        max_num = max(max_num, int("".join(N)))
        return max_num

    for i in range(M - 1):
        for j in range(i + 1, M):
            if i == 0 and (N[j] == '0'):
                continue

            N[i], N[j] = N[j], N[i]

            if ("".join(N), c) not in visited:
                dfs(c - 1)
                visited.add(("".join(N),c))

            N[i], N[j] = N[j], N[i]




if M <= 2 and M - N.count("0") <= 1:
    print(-1)
else:
    dfs(K)
    print(max_num)