[파이썬] 15650번. N과 M (2) 풀이

재귀함수는 너무 어렵다..

이전 15649번 문제도 한참 해맸는데, 조금만 응용하니까 더 헷갈린다.

 

처음 직접 풀었던 풀이 -> 그냥 이전 풀이처럼 모든 가능한 경우의 수를 다 때려박고

바로 출력하는 대신, 수열을 강제로 정렬하고 set으로 중복을 제거하고, 다시 출력했다.

딱 봐도 N, M이 커지면 커질 수록 시간 복잡도에서 손해를 볼 것이 분명하다..

 

N, M = map(int, input().split())
seq = [] 
seq_list = [] # 문제의 조건을 만족하는 수열들이 담길 리스트 

def dfs():
    if (len(seq) == M):
        seq_list.append(sorted(seq)) # 수열을 강제로 정렬한다음 리스트에 넣는다.
        return
    
    for i in range(1, N + 1):
        if (i not in seq): # 같은 수 중복을 방지하기 위해
            seq.append(i)
            dfs()
            seq.pop() # pop()은 리스트의 맨 마지막 원소를 리턴하고 그 원소는 삭제한다.

dfs()

# 원소가 list일 때도 set으로 중복을 제거하고 싶다면 map()으로 tuple로 바꾸면 할 수 있다.
seq_list = list(set(map(tuple, seq_list)))
seq_list.sort()
for seq in seq_list:
    print(" ".join(map(str, seq)))

 

---

인터넷 풀이를 참고한 2번째 방법 -> dfs() 함수를 살짝 변형해서, 반복문이 1 ~ N까지 모든 숫자를 사용하지 않고

앞의 숫자가 뒤의 숫자보다 큰 경우를 제외하기 위해 start부터 N까지의 숫자를 사용한다.

이 방법은 아예 반복문이 적게 실행된다는 장점이 있다!

 

N, M = list(map(int,input().split()))
seq = []

def dfs(start):
    if (len(seq) == M):
        print(' '.join(map(str, seq)))
        return
    
    # 기존에는 1부터 N까지 모든 숫자를 사용했지만, 이제는 [2, 1]같은
    # 앞의 숫자가 뒤의 숫자보다 큰 경우를 제외하기 위해 start부터 N까지의 숫자를 사용한다.
    for i in range(start, N + 1):
        if i not in seq:
            seq.append(i)
            dfs(i + 1)
            seq.pop()
            
dfs(1)

 

보아하니

앞으로의 백트래킹 유형 문제들이 나에게는 정말 쉽지 않을 것 같다 ㅠㅠ

 

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)