[Python][백준/BOJ] 15663번 : N과 M (9)

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

15663번: N과 M (9)

 

내 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num = sorted(list(map(int, input().split())))
tmp = []
visited =[False for _ in range(1000001)]

def dfs():
    start =0
    if len(tmp) == m:
        print(*tmp)
        return

    for i in range(n):
        if not visited[i] and start != num[i]:
            tmp.append(num[i])
            visited[i]=True
            start = num[i]
            dfs()
            visited[i]=False
            tmp.pop()
dfs()

 

다른 풀이(SET 이용)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num = sorted(list(map(int, input().split())))
tmp = []
visited =[False for _ in range(1000001)]
ans =[]
def dfs(start):
    if len(tmp) == m:
        ans.append(tmp[:])
        return
    
    for i in range(n):
        if not visited[i]:
            tmp.append(num[i])
            visited[i]=True
            dfs(num[i])
            visited[i]=False
            tmp.pop()
dfs(0)
ans = sorted(list(set(map(tuple, ans))))
for i in ans:
    print(*i, sep=' ')

 

dfs, 같은 수라면 한 번만! 순열

푸는데 많은 시간 동안 붙잡고 고민했다..

이번 문제는 9 7 9 1이라는 수를 입력받으면 9 9는 한 번만 출력되어야 한다. 그런데 내 코드는 계속 9 9가 두 번 출력되었다.

그래서 이걸 해결하기 위해 두 조건을 만들었다.

1. prev 라는 변수에 바로 직전의 수를 저장하고, 그 수와 현재의 수가 같은지 검사
2. visited를 통해 이미 방문을 했는지 안했는지 검사

이 두 조건을 동시에 만족하는 수열만이 통과할 수 있도록 했다.

그리고 이를 저장한 후 SET로 중복 제거를 해주었다.