[Python] 15666 N과 M(12)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

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

출력

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

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

문제 풀이

A. 접근

N과 M의 마지막 시리즈. 이번에는 입력이 중복, 같은 수를 여러 번 고를 수 있으며, 비내림차순으로 출력해야 한다.

백트래킹으로 답을 구하는 것이며, 중복된 숫자가 입력으로 주어지기 때문에 중복되는 수열을 제거할 딕셔너리나 집합 자료형을 사용한다. 또한, 비내림차순으로 출력해야 하기에 for 반복문으로 작성하고 시작 인덱스를 적절히 조절하도록한다.

B. 코드 분석

전체 코드

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

arr = []
dict = {}

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

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

solve(0, 0)

B-1. 준비

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

arr = []
dict = {}

사전순으로 출력해야 하고, 비내림차순이기도 해서 sorted 함수로 정렬된 리스트를 반환받는다. 이때, ''.join()을 원활하게 하기 위해서 따로 자료형을 변환하지 않았다.

arr은 출력을 위해 사용할 배열, dict는 중복을 제거하기 위한 자료형이다.

B-2. 풀이

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

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

solve(0, 0)

Base Condition은 cnt 즉, 반복이 주어진 m만큼 반복되었을 때(정해진 수열의 길이를 충족했을 때) 자료형에서 값을 찾고, 값이 없는 것은 중복이 없는 것이므로 값을 추가한 후 출력한다.

for 반복문에서 시작 인덱스를 지정하도록 한다. 시작 인덱스는 idx로, idx는 이전 재귀에서온 인덱스이다. 이렇게 설정한 이유는 정렬을 통해 리스트가 오름차순이며 동일한 수를 중복해서 고를 수 있기 때문에 선택한 인덱스에서 다시 선택을 시작하게 반복문을 설정한다.

총평

백트래킹 간단한 문제는 이제 할 만하다 ㅎㅎ