[BOJ 1039] 교환 - Python 풀이

 

문제

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

코드

import sys

def get_biggest_number(n, k):
    answer = -1
    len_str_n  = len(n)

    if len_str_n <= 1 or (len_str_n == 2 and n[1] == '0'): return -1
    if k == 0: return n

    visited = [[False for _ in range(11)] for _ in range(1000001)]
    q = []
    q.append([[num for num in n], 0])
    visited[int(n)][0] = True

    while q: 
        num, depth = q.pop()

        if depth == int(k):
            answer = max(answer, int("".join(num)))
            continue
        
        for i in range(len_str_n):
            for j in range(i+1, len_str_n):
                if i == 0 and num[j] == '0': continue

                temp = num[i]
                num[i] = num[j]
                num[j] = temp

                num_int = int("".join(num))

                if not visited[num_int][depth+1]:
                    visited[num_int][depth+1] = True
                    q.append([num.copy(), depth+1])
                
                temp = num[i]
                num[i] = num[j]
                num[j] = temp
    
    return answer


if __name__ == "__main__":
    n, k  = sys.stdin.readline().split()
    print(get_biggest_number(n, k))

풀이

처음에는 그냥 구현하는건가? 해서 구현하는 방식의 코드로 했다가 반례가 너무 많아져서 어떻게 해야 할까 고민하다가 도저히 모르겠어서 질문 게시판을 찾아봤다.

질문 게시판에서 다들 bfs로 구현했다고 하길래 엥 bfs로 어떻게?? 이런 생각이 들었다.

bfs가 뭔지도 알고 bfs의 기본 틀도 알고는 있지만

어떤 문제에 적용시켜야 하는지, 그리고 어떻게 문제 상황에 적용시켜야 하는지 모르는 것을 보니 bfs 양치기가 필요하다는 생각이 들었다. bfs 문제집만 냅다 풀어야겠다ㅠ 그러다보면 잘하게 되겠지..

결국 이번에도 모르겠어서 이분의 코드를 참고해서 구현했다. (링크 참고)

visted 리스트를 만드는데 시간이 꽤 오래 걸려서 엥 이게 되나 싶지만 된다. N이 최대 1,000,000이고 K가 최대 10이므로 O(N^2)의 시간복잡도를 가진다고 해도 10,000,000회 연산을 하므로, 문제의 시간제한이 2초보다 적게 걸린다.

bfs를 더 공부해야겠다..