[Python] 15665 N과 M(11)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

문제 풀이

A. 접근

백트래킹을 사용하는 전형적인 문제. N과 M이 벌써 다 끝나간다.

같은 수를 여러 번 고를 수 있지만, 동일한 수열이 나오면 안 된다. 그렇기 때문에 맵 혹은 딕셔너리를 만들어서 중복되는 수열을 제거하는 것이 좋다.

백트래킹으로 값을 넣고 빼면서 해를 찾아나가야 한다.

B. 코드 분석

전체 코드

n, m = map(int, input().split())
num = sorted(input().split(), key=lambda x: int(x))

arr = []
dict = {}

def solve(cnt):
    if cnt == m:
        k = ' '.join(arr)
        if k not in dict:
            dict[k] = 1
            print(k)
        return

    for i in range(n):
        arr.append(num[i])
        solve(cnt + 1)
        arr.pop()

solve(0)

B-1. 준비

n, m = map(int, input().split())
num = sorted(input().split(), key=lambda x: int(x))

arr = []
dict = {}

사전 순으로 출력해야 하기에 정렬을 해주었으며, ' '.join() 방법을 원활하게 사용하기 위해 따로 자료형 변환은 하지 않았다. 임시로 사용할 리스트인 arr을 만들고, 중복을 제거하기 위한 딕셔너리 dict도 만들어주었다.

B-2. 풀이

def solve(cnt):
    if cnt == m:
        k = ' '.join(arr)
        if k not in dict:
            dict[k] = 1
            print(k)
        return

    for i in range(n):
        arr.append(num[i])
        solve(cnt + 1)
        arr.pop()

solve(0)

Base Condition으로 dict안에 해당 수열이 없다면 값을 저장한 후 출력하도록 하였다. 매번 재귀를 돌면서 수열을 만든다. 같은 수를 여러 번 골라도 되고 내림차순도 신경쓰지 않아도 돼서 편하게 반복문을 작성했다.

총평

N과 M은 백트래킹 익숙해지는 데에 참 좋은 문제같다.

주로 구조가

def func(k):
    if k == n:
        # 구한 해
        return

    for i in range(a):
        # 해를 구하기 위한 조건 추가
        func(변경 혹은 추가된 인자)
        # 원상태로 복귀

이러한 형태를 가진다.