[Baekjoon] 15663 번 : N과 M (9) (Python, 백트래킹, 정렬)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Contribute to stellaluminary/Baekjoon development by creating an account on GitHub.

github.com

Python

시간 초과 - 방법 1 - 코드 길이 517B

처음 시도했던 방법은 counting을 통해 백트래킹을 진행한 것이다.

그러나 많은 시간이 소모되어 시간 초과가 나왔다.

def dfs(idx):
    global m
    if idx == m:
        if s not in res:
            res.append(copy.deepcopy(s))
        return

    for i in l:
        if o[i] != 0:
            s.append(i)
            o[i] -= 1
            dfs(idx+1)
            s.pop()
            o[i] += 1

import sys
import copy
input = sys.stdin.readline

n,m = map(int, input().split())
l = sorted(list(map(int, input().split())))
s = []
o = {i:0 for i in l}
for i in range(len(l)):
    o[l[i]] += 1

res = []
dfs(0)
for i in res:
    print(*i)

방법 2 - 메모리 30840KB / 시간 136ms / 코드 길이 454B

깊이가 깊어짐에 따라 해당 depth에서의 겹침이 존재하는지 존재한다면 생략하는 방향으로 진행한다.

이때 visit을 통한 활용과 더불어 overlap을 사용한다.

def dfs(idx):
    global n, m
    if idx == m:
        print(*s)
        return

    overlap = 0
    for i in range(n):
        if not visit[i] and overlap != l[i]:
            visit[i] = 1
            s.append(l[i])
            overlap = l[i]
            dfs(idx+1)
            visit[i] = 0
            s.pop()

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
l = sorted(list(map(int, input().split())))
visit=[0]*n
s = []

dfs(0)