N 과 M 9

간단한 DFS문젠줄 알았는데, 생각보다 시간을 많이 썻다.

중복되는 수열을 여러 번 출력하면 안되서 무턱대고 아래와 같이 if ~ not in ~을 사용해서 중복 수열을 확인하면 시간초과가 발생한다.

    if cnt == m:
        tmp = list(num[i] for i in numbs)
        if tmp not in answer:
            answer.append(tmp)
        return

따라서, 이렇게 시간 복잡도가 큰 방법 말고 다른 방법을 사용해야 했는데 이를 생각하기가 쉽지 않았다. 결국 구글링을 통해 힌트를 얻었다…

m개를 고른 후에 중복되는 수열을 거르는 것이 아니라, 애초에 중복되는 수열을 만들지 않게 해야했다.

same이라는 변수를 활용해 이를 해결했다.

for 문을 돌며 배열에 원소들을 추가해 준다. 이때 값이 같은 원소의 경우 여러번 추가되게 되면 중복되는 수열이 생성됨으로, 값이 같은 원소인 경우에 딱 한 번만 추가해 수열을 생성하도록 한다.

same 변수에 이전에 추가된 원소의 값을 저장한 후, 다음에 추가될 원소의 값과 비교해 값이 다를 경우에만 수열에 추가한다.

def DFS(cnt,numbs):
    if cnt == m:
        answer.append(numbs)
        return
    #same 변수를 활용해 중복되는 수열을 생성하지 못하게 해주었다.
    same=0
    for i in range(n):
        if check[i] and same != num[i]:
            check[i]=False
            DFS(cnt+1, numbs+[num[i]])
            check[i]=True
            same=num[i]


CODE

import sys
read = sys.stdin.readline

n, m = map(int, read().split())
num = list(map(int, read().split()))
#사전 순으로 증가하는 순서로 만들기 위해 오름차순 정렬을 해준다.
num.sort()
#m개를 고른 수열 저장
answer = []


def DFS(cnt,numbs):
    if cnt == m:
        answer.append(numbs)
        return
    #same 변수를 활용해 중복되는 수열을 생성하지 못하게 해주었다.
    same=0
    for i in range(n):
        if check[i] and same != num[i]:
            check[i]=False
            DFS(cnt+1, numbs+[num[i]])
            check[i]=True
            same=num[i]

#해당 원소가 수열에 포함되었는지 체크
check = list(True for _ in range(n))
DFS(0, [])
for a in answer:
    print(*a)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]