백준 N과 M(9) - 15653번

문제 링크 : 백준 N과 M(9) 15653번

이 문제는 itertools패키지를 사용하여 풀어본 풀이 + 백트래킹을 사용하여 푼 풀이 두 가지 방법을 보여드릴려고 한다.

itertools패키지의 permutation 클래스를 이용한 풀이

from itertools import permutations
import sys
input = sys.stdin.readline

# itertools를 사용하여 푼 풀이
n,m = map(int, input().split())

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

result = []

result.extend(permutations(lst,m))

result = list(set(result))

result.sort()

for ans in result:
    print(*ans)

백트래킹을 사용하여 풀어본 풀이

#백트래킹을 사용해서 푼 문제
import sys
input = sys.stdin.readline

n,m = map(int, input().split())

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

visited = [False] * len(lst)

ans = []

result = []

def dfs(depth):
    
    if depth == m:
        result.append(tuple(ans))

        return

    for i in range(len(lst)):
        if not visited[i]:
            visited[i] = True
            ans.append(lst[i])
            dfs(depth+1)
            # 해당 노드에 대해서만 False 해주어서 모든 순열을 다 따질 수 있게 해준다. 
            visited[i] = False
            ans.pop()


dfs(0)

# 중복되는 값들이 있으면 set 자료구조를 통해 없애주고 다시 list로 감싼다. 
result = list(set(result))

# result안에 있는 값들을 sort()
result.sort()

for answer in result:
    print(*answer)

한 가지 간과했던 사실

tuple자료형은 리스트와 다르게 수정이 불가능하여 값 자체를 의미하는 경우를 뜻하는데 만약 튜플자료형 값들을 담아둔 list에 sort()함수를 사용할 경우 모든 자릿수에 대해서 오름 차순을 해준다.

sort(key = lambda x : (x[0],x[1],x[2] ... ))

람다식에서 이렇게 ()로 묶어서 정렬했듯이 튜플 값에 대해 정렬하게 되면 각각의 자릿수에 대해서 각각 오름차순이 가능하다는 것을 간과했다. 리스트에 대해서 sort할 경우 제일 앞 자리에 대해서만 sort한다.