[BOJ][⚪2][백준#15664] N과 M (10)

문제 출처

BAEKJOON Online Judge #15664

문제

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

N개의 자연수 중에서 M개를 고른 수열 고른 수열은 비내림차순이어야 한다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 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 9
9 9

예제 3

입력

4 4
1 1 2 2

출력

1 1 2 2

My Sol

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

def f():
    if len(stack)==M:
        print(*stack)
        return

    check = 0
    start = stack_k[-1] if stack_k else 0
    for k in range(start, N):
        if not visited[k] and check != nums[k]:
            check = nums[k]
            stack_k.append(k)
            visited[k] = 1
            stack.append(nums[k])
            f()
            stack_k.pop()
            visited[k] = 0
            stack.pop()

visited=[0]*N
stack = []
stack_k = []
f()

stack_k로 재귀함수 내에서 nums의 k, 즉 몇 번 인덱스부터 시작할 것인지에 대해 저장한다. for문의 k의 시작인 start를 조건에 따라 stack_k에 값이 없다면 0으로, 있다면 stack_k[-1]로 설정하여 이전 인덱스부터 시작하는 일이 없도록 한다.

중복을 허용하지 않으므로 visited 개념을 도입하여 이미 stack에 추가한 k는 사용하지 않고 다음 k로 넘어가도록 하였으며, depth가 M에 도달하면 stack을 출력 형식에 맞게 출력한 뒤, stack_k, stack에서 마지막 항목을 pop하고 visited[k]를 0으로 되돌린다.

결과

맞았습니다!!

모범답안

출처

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

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

dfs(0)

재귀함수에 parameter로 시작할 때는 0을 전달하여 for문의 인덱스가 0부터 시작하게 하고, 이후 depth부터는 인덱스+1을 주어 stack_k 없이 다음 k부터 조회를 시작하도록 하였다.