[BOJ] 15650

문제

me

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
nums_set=set() # 중복 거르기 위해 set 이용 
def findPerm(nums=[]):
    global nums_set
    if len(nums)==M:
        nums_set.add(tuple(sorted(nums))) # 같은 집합임을 보이기 위해 sort 하여 순서를 맞춤
        return
    else:
        for i in range(1,N+1):
            if i not in nums:
                nums.append(i)
                findPerm(nums)
                nums.pop()

findPerm()
nums_set=sorted(list(nums_set))
for nums in nums_set:
    print(*nums)

기존 N과M에서 set을 이용하면 되겠지! 했는데
tuple로 원소를 넣어야 한다는 점과 순서가 같아야 같은 걸로 인식한다는 문제로 sort마저 써버렸다.
결론은 시간 측면에서 아주 비효율적이다.

기존에서 줄일 방법도 있을 텐데
오히려 sort를 통해 매번 O(M)이 돈다..
차라리 tuple 말고 set을 써도 좋았을 것 같다.

solution

n,m = list(map(int,input().split()))
s = []
def dfs(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start,n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)

start를 통해

1을 통해서 다음 재귀를 갔다면 2부터 시작하게 하면서 1에 대해서 처리하지 않도록 함

참고