[Baekjoon 15664 / Python / 실버2] N과 M (10)

문제

import sys

input = sys.stdin.readline

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

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

numbers.sort()

visited = [False] * N

result = [-1] * M

def compare(a, b):

    if a > b:

        return False

    return True

def backTracking(depth):

    if depth == M:

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

        return

   

    temp = 0

    for i in range(N):

        if (depth == 0 and temp != numbers[i]) or (not visited[i] and temp != numbers[i] and compare(result[depth - 1], numbers[i])):

            visited[i] = True

            temp = numbers[i]

            result[depth] = numbers[i]

            backTracking(depth + 1)

            visited[i] = False

   

backTracking(0)

 

N과 M 9번에서 한참 헤맸으나 해결하고 나니 10번부턴 다시 쉬워졌다.

 

다만 9번 문제처럼 temp 변수를 이용해 중복 순열을 제거했는데도 중복 순열이 나오길래 뭐가 문제지 싶었는데,

depth가 0일 때도 temp변수를 통해 중복을 제거해야 한다는 걸 깨달았다.

이후 조건문을 고쳐주니 바로 통과되었다.