[Baekjoon 15666 / Python / 실버2] N과 M (12)

문제

import sys

input = sys.stdin.readline

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

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

numbers.sort()

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 temp != numbers[i] and (depth == 0 or compare(result[depth-1], numbers[i])):

            temp = numbers[i]

            result[depth] = numbers[i]

            backTracking(depth + 1)

   

backTracking(0)

 

드디어 N과 M 문제들이 끝났다. 백트래킹 공포증 때문에 시작했던 건데, 이제 백트래킹의 틀 정도는 꽤 익숙해진 것 같다.

 

비내림차순을 검사하는 compare 함수를 만든다.

depth가 M에 도달하면 만들어진 수열을 출력한다.

temp 변수를 사용해, 중복 수열이 만들어지는 것을 방지한다. 같은 depth에서 같은 값을 사용하지 않게 함으로써 방지된다.

numbers 리스트는 정렬되어 있으므로, 이전에 사용한 값과 현재 사용할 값만 비교하면 된다.