[백준/1039/파이썬] 교환

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

1039번: 교환

Problem

0으로 시작하지 않는 정수 N이 주어진다. i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

조건

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

SOL

자릿수를 K번 바꿨을때,만들 수 있는 가장 큰 수를 출력하면 되는 시뮬레이션 문제.

하지만, 자릿수를 k번 바꾼다는건 생각보다 많은 경우의 수를 요구한다.

 

처음 푼 방법

자릿수가 n인 정수가 있을 때, n의 자릿수를 바꿔서 나올 수 있는 경우의 수는 n=5면, 5+4+3+2+1. 즉, n(n+1)/2 경우의 수가 발생되며, O(n^2)이라고 볼 수 있음. 이 경우에는, 자릿수를 1번, 2번,3번...K번까지 바꿔야하므로, 방문 chk배열의 크기가 엄~~~청 커질 수 밖에 없을거 같음.

단순히 선형적으로 푼다고 하면, visited는 아마, 10*1,000,000의 크기로 준비해야할듯함.

하지만, 이 방법으로 못푸는건 아님!!. 메모리 공간은 충분하므로, 이렇게 풀 수 도 있음. 이때, 시뮬레이션에 필요한 dq에는 , N과 카운트하는 변수가 같이 들어있을 거임.

=> 저도 처음에는 이 방법으로 풀었습니다.

from collections import deque
N,K = input().split()

M= len(N)
K = int(K)
v_chk=[[False]*11 for i in range(1000001)]
q=deque()
q.append([[ch for ch in N],0])

v_chk[int(N)][0]=True

def swap(N, idx1, idx2):
    temp = N[idx1]            
    N[idx1] = N[idx2]
    N[idx2] = temp
    
answer= -1
def bfs():
    ans=-1
    while q:
        n,cnt=q.popleft()
        if cnt==K:
            ans=max(ans,int("".join(n)))
            continue
        for i in range(M):
            for j in range(i+1,M):
                if i==0 and n[j] =='0':
                    continue
                swap(n,i,j)
                n_int=int(''.join(n))
                if not v_chk[n_int][cnt+1]:
                    v_chk[n_int][cnt+1]=True
                    q.append([n.copy(),cnt+1])
                swap(n,i,j)
    return ans
answer=bfs()
print(answer)

좀 더 생각을 하고, 개선된 풀이

combination 응용 + set로 방문 chk + swap하는 방법 파이썬 내부 기능 이용

1. 먼저 자리를 교체할 후보를 선정해보자.  자릿수가 n일 때, 2개를 뽑는 경우 => nC2 

2. K번 동안, 해당 후보들을 가지고, 시뮬레이션을 돌리고, 그 중에서 제일 큰 값을 뽑아오는 형식으로 구현해볼거임.

3. visited는 방문하는 애들만 등록하는 형식으로, set형식으로 만들어 줄 거임.

4. 만약, ans가 그대로 0이면, 바꿔도 작아지기만 하는거니까, -1을 출력하게 해줄거임.

from collections import deque
from itertools import combinations
import sys
import copy
input = sys.stdin.readline

def bfs():
    visited=set()
    ans=0
    for _ in range(len(dq)):
        x=dq.popleft()
        num=list(str(x))
        for i,j in idx:
            s=copy.deepcopy(num)
            s[i],s[j] = s[j],s[i]
            if s[0] =='0':
                continue
            nx = int(''.join(s))
            if nx not in visited:
                ans=max(ans,nx)
                visited.add(nx)
                dq.append(nx)
    return ans


N,K = map(int,input().split())
item = [ch for ch in range(len(str(N)))]
#print(item)
idx = list(combinations(item,2))
dq= deque()
dq.append(N)
ans=0

while K:
    ans = bfs()
    K -=1

if not ans:
    print(-1)
else:
    print(ans)