백준 알고리즘 15663 (N과 M(9)) - python

[문제] 백준 알고리즘 15663 (N과 M(9)) - python

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

15663번: N과 M (9)

 

이제는 N개의 자연수 중에 겹치는 수가 존재할 수 있는 문제다.

 

결론부터 말하면 처음에는 시간초과로 계속 실패했다. (pypy3로는 간신히 통과)

접근법 자체가 문제는 아니었고, 원인은 python에서 편리하게 쓰는 'if A in B' 이다.

이 구문이 A가 B배열 안에 소속되어 있는지를 검사하기 위해 for문이나 재귀 함수에서 쓰일 때,

아마도 소요 시간이 급증한 것 같다. 조심해야겠다.

 

[Code]

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

L.sort()
visited = [False] * N
out = []
all_out = []

def solve(depth, N, M):
    if depth == M:
        tmp = ' '.join(map(str, out))
        if tmp not in all_out:
            all_out.append(tmp)
        return
    for i in range(N):
        if not visited[i]:
            out.append(L[i])
            visited[i] = True
            solve(depth+1, N, M)
            out.pop()
            visited[i] = False

solve(0, N, M)
for i in all_out:
    print(i)

 

그래서 방법을 바꿔서, 효율적이게 중복 조합을 제거하는 방법을 썼다.

overlap이란 변수를 만들어서 전에 쓰인 변수 값과 비교하는 것이다. (초기값 0, 자연수가 아니므로)

위치는 탈출문 바로 아래쪽에 위치하게 했는데, 이유는 깊이가 다를 때마다 변수를 초기화해야하기 때문이다.

그리고 방문 여부를 확인과 동시에 값도 이전에 쓰인 변수 값과 같은지 확인해주고

DFS를 진행하기 직전에 지금의 변수 값을 넘겨주었다.

 

[Code]

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

L.sort()
visited = [False] * N
out = []

def solve(depth, N, M):
    if depth == M:
        print(' '.join(map(str, out)))
        return
    overlap = 0
    for i in range(N):
        if not visited[i] and overlap != L[i]:
            visited[i] = True
            out.append(L[i])
            overlap = L[i]
            solve(depth+1, N, M)
            visited[i] = False
            out.pop()

solve(0, N, M)