[Baekjoon 15663 / Python / 실버2] N과 M (9)

문제

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

visited = [False] * N

numbers = list(map(int, input().split()))

numbers.sort()

result = [-1] * M

def backTracking(depth):

    if depth == M:

        print(' '.join(map(str, result)))

        return

   

    # temp 변수를 활용하여 완성된 중복 순열을 방지한다.

    temp = 0

    for i in range(N):

        if not visited[i] and temp != numbers[i]:

            result[depth] = numbers[i]

            visited[i] = True

            temp = numbers[i]

            backTracking(depth + 1)

            visited[i] = False

backTracking(0)

 

여기서 애좀 먹었다. 별거 아닌 거 같은데 입력값으로 중복된 숫자가 들어오기 때문에 까다롭다.

따라서 완성된 중복 순열을 배제하는 게 매우 헷갈린다.

 

visited를 사용하면 중복된 숫자가 들어오더라도 각 1번씩 사용되기 때문에 중복 순열이 생성되지 않을 것 같지만,

주어진 수가 [1, 7, 9, 9] 라고 했을 때,

1이 선택된 상태로 9가 선택되어 1 9 순열이 완성되고 리턴된 후 이어서 다시 9가 선택되면 또다시 1 9 순열이 생겨버린다.

즉, 같은 depth에서 같은 숫자를 사용하지 않도록 해야 한다.

 

그렇게 하는 방법은, numbers를 정렬하면 같은 숫자들은 모여있게 되기 때문에 같은 depth에서 이전에 사용했던 숫자를 temp에 저장해 두고, 그 숫자가 아닐 때 순열을 만드는 것이다. 모여있기 때문에 바로 이전 값만 저장해서 비교해도 문제없다.

 

N과 M 풀면서 여기서 처음으로 막혔다 ㅠ