[Python] 15664 N과 M(10)

문제

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

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

입력

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

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

출력

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

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

문제 풀이

A. 접근

15663 N과 M(9) 문제에서 비내림차순이라는 조건이 추가되었다.

입력이 중복으로 주어지기 때문에 같은 출력은 배제해야 한다. 백트래킹을 사용해서 문제를 풀어보도록 하자.

백트래킹은 가장 깊이 들어가서 해를 찾고 뒤로 나오면서 다시 해를 찾아가는 방법이다. 시도할 수 있는 모든 수단을 사용하고, 다시 뒤로 돌아와 할 수 있는 모든 가지 수를 새로 시도한다. 코드를 보며 같이 확인하자.

B. 코드 분석

전체 코드

import sys
input = sys.stdin.readline
print = sys.stdout.write

n, m = map(int, input().split())
arr = sorted(input().split(), key=lambda x: int(x))
num = []
dict = {}

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

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

solve(0, 0)

B-1. 준비

import sys
input = sys.stdin.readline
print = sys.stdout.write

n, m = map(int, input().split())
arr = sorted(input().split(), key=lambda x: int(x))
num = []
dict = {}

먼저 출력이 많을 수 있으니 sys.stdout.write로 출력하도록 한다.

또한, 출력은 사전순으로 해야 하기 때문에 먼저 sorted함수를 사용해서 정렬한다. 이때, 사전순으로 해야 하기 때문에 key에서는 lambda를 통해 int로 정렬했다.

num은 출력할 때 사용할 리스트이고, dict는 중복을 검사하기 위한 딕셔너리이다.

B-2. 풀이

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

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

solve(0, 0)

    if cnt == m:
        k = ' '.join(num)
        if k not in dict:
            dict[k] = 1
            print(k + '\n')
            return

이부분은 m 길이의 수열을 만들었을 때, 이것이 이미 출력을 했던 값인지 확인하기 위해 딕셔너리에서 찾아보고 없다면, 값을 추가한 다음 출력한다.(최종적으로 출력해야 할 Base Condition)

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

solve(0, 0)

Base Condition에 다가가기 위해 반복문을 작성한다. 여기서 정렬을 미리 해두었으므로, 바로 append를 하고 i보다 1 큰 값으로 함수를 재실행하여 비내림차순으로 탐색할 수 있도록 한다.

총평

고려할 것이 꽤 늘어난다. Base Condition을 어떻게 설정해야 하고, Base Condition을 위해 어떤 시퀀스를 거쳐야 하는지도 고려해야 할 점이다. 왜 백트래킹이 어렵지만, 그 매력에 빠지면 헤어나올 수 없다는지 이해되려고 한다.