[백준 1039] 교환(Python)

1039번: 교환

정수 N이 있습니다.

i자리의 수와 j자리의 수를 서로 바꾸는 작업을 K번 반복해서 나온 수들 중, 최댓값을 구하는 문제 입니다.

DP+브루트포스로 푸는 방법과 그래프 탐색으로 푸는 방법이 존재하지만 원리는 거기서 거기이기 때문에 여기선 그래프 탐색으로 푸는 방법만 설명하려고 합니다.

사실 N, K범위가 작기 때문에 브루트포스 방법이 먹혔던 거지 범위가 길었으면 시간초과가 발생 할 풀이 입니다.

그리디가 아닌 이유

얼핏 보면 그리디 처럼 보입니다. 수들을 이리저리 움직여서 수의 최대값을 맞추는 문제 처럼 보이기 때문입니다. K번 이내에 최댓값을 구하라는 문제였다면 그리디로 풀렸을 지도 모릅니다. 왜냐하면 1 ~ K번사이 안에 최대값으로 맞추거나 근접하게 맞추면 되기 때문입니다. 하지만 조건에서는 딱 K번 이후에 값들 중 최대 값을 구하라고 명시가 되어 있습니다. 중간에 최대값으로 맞춰나도 횟수가 남아있으면 어쩔 수 없이 수들을 바꿔야 합니다. 그렇기 때문에 그리디로는 풀기가 힘들 수 있습니다.

풀이

풀이 방법은 간단합니다. 맨 처음 입력 받은 N을 set에 추가하고 K번동안 스왑 작업을 돌리면 됩니다. 이렇게 되면 너무 많은 데이터가 쌓여서 메모리가 터질것 같아 보이지만, 파이썬의 set은 같은 값을 가지지 않기 때문에  메모리가 터질 일은 없습니다.

작업을 다 끝내고 set에 남아있는 데이터를 확인합니다. 없으면 작업이 불가능한 상태이므로 -1을 출력하고 있으면 정렬을 해서 이 중 최댓값을 출력하면 됩니다.

 

코드 보기

import sys
input = sys.stdin.readline

n, k = map(int, input()[:-1].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)