[BOJ][⚪2][백준#15663] N과 M (9)

문제 출처

BAEKJOON Online Judge #15663

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제

예제 1

입력

3 1
4 4 2

출력

2
4

예제 2

입력

4 2
9 7 9 1

출력

1 7
1 9
7 1
7 9
9 1
9 7
9 9

예제 3

입력

4 4
1 1 1 1

출력

1 1 1 1

My Sol

def f(i, N, M):
    global nums
    global stack
    global accum
    global visited

    if i == M:
        if stack==accum[-1]:
            print(*stack)
            accum.append(stack[::])
        return

    for k in range(N):
        if visited[k]==1:
            continue

        visited[k] = 1
        stack.append(nums[k])
        if stack not in accum:
            accum.append(stack[::])
            f(i+1, N, M)
        visited[k] = 0
        stack.pop()

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

stack = []
visited = [0]*(N+1)
accum = []

f(0, N, M)

그동안 해오던 방식대로 depth를 i로 두고 1씩 올리다가 이 i가 M에 다다르면 stack을 출력하는데, 기존과 달리 accum의 마지막 인덱스 리스트가 stack인, 즉 stack을 모두 완성하기 전까지 accum에 stack이 없었다면 stack을 출력 형식에 맞게 출력하고 stack을 accum에 추가한다.

0부터 N-1의 모든 수 k에 대하여 visited가 1이라면 다음 k로 넘어가고 이 k를 nums의 인덱스로 하여 stack에 추가하는데, 중복을 허용하지 않으므로 accum에 이 stack과 같은 리스트들이 있다면 그 이후는 무의미하므로 다음 k로 넘어가게 된다.

매 depth마다 stack을 accum에 넣고 visited를 체크하고 다음 재귀함수를 호출하는 방식으로 결국 이전에 이와 같은 패턴의 stack이 나왔었는지를 매번 체크하는 방식이다.

결과

시간초과

체크 리스트를 매번 만들고, in 함수를 써서 O(N2)의 시간복잡도를 가지는 것이 패인이었던 것 같다. 오래 고심해보아도 다른 방법이 통 생각이 나지 않아서 블로그의 풀이를 참고하였다.

모범답안

출처

n, m = map(int, input().split())
nums = sorted(list(map(int, input().split())))
visited = [False] * n
temp = []

def dfs():
    if len(temp) == m:
        print(*temp)
        return
    remember_me = 0
    for i in range(n):
        if not visited[i] and remember_me != nums[i]:
            visited[i] = True
            temp.append(nums[i])
            remember_me = nums[i]
            dfs()
            visited[i] = False
            temp.pop()

dfs()

n과 m, nums로 입력을 받아 처리하고, 중복을 허용하지 않기 위해 visited를 사용하였다. stack의 의미로 temp를 사용하였다.

인상적인 점은 재귀함수에 인자를 넣지 않는다는 점이었다. 종료 base 조건은 len(temp)가 M일 때로 하였기 때문에 depth 인자가 필요하지 않은 것이다.

0부터 n-1까지의 수 i를 인덱스로 하여 visited에 해당 i가 방문하지 않았고, remember_me가 i를 인덱스로 하는 nums의 값이 아니라면 재귀를 진행한다. remember_me는 해당 depth에서 nums[i]이 이전 조건을 만족하는 i’를 인덱스로하는 nums[i’]와 같은 값이라면 진행할 필요가 없으므로 다음 i로 넘기는 것이다. 다음 depth에서는 remember_me는 새롭게 시작한다.

나는 생각치도 못한 신박한 방법으로 중복 문제를 해결하셨다.