백트래킹?

#15663번 N과M (9) https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

비슷한 유형의 문제를 연달아 풀고 있는 중이다.

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

output = []
visited = [False]*N


def solve(depth, n, m):
    if depth == m:
        r = ' '.join(map(str, output))
        print(r)
        return
    overLap = 0
    for i in range(n):
        if not visited[i] and nums[i] != overLap:
            output.append(nums[i])
            visited[i] = True
            overLap = nums[i]
            solve(depth+1, n, m)
            visited[i] = False
            output.pop()


solve(0, N, M)

 

이 문제는 그래프 탐색을 기반으로 한다. 2개의 순열을 만들 때는 깊이가 2인 깊이우선탐색을 한다고 생각하면 될 것 같다.

 

이 문제에서 헷갈렸던 점은 출력되는 순열이 중복되어선 안된다는 부분이다.

 

첫 번째 시도에서는 리스트를 만들어서 출력값들을 저장하고 in을 통해서 점검하는 방식을 택했다.

역시나 시간초과

in은 리스트 내의 모든 요소들과 비교를 진행하기 때문에 대부분의 연산에서 O(리스트의 길이)만큼의 시간복잡도가 생긴다. ( O(n) )

 

검색을 통해 조금 더 현명한 방법을 찾았다.

 

1) 숫자 리스트는 기본적으로 정렬한 채로 진행한다.

2) 때문에 같은 수는 연달아 존재한다. [ 1, 1, 2, 2 ]...

3) 그러므로 이전에 나온 수만 저장한 뒤 그 수와 같은 경우만 제외해주면 된다.

 

코드를 재사용하다보니 리스트를 정렬했다는 사실을 까먹은 채로 진행한게 흠이었다.

되도록이면 처음부터 다시 짜는게 좋을 듯 하다.