[Python] 15663 N과 M(9)

문제

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

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

입력

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

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

출력

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

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

문제 풀이

A. 접근

기존 N과 M 문제에서 살짝 디테일한 부분을 고려해야 한다. 먼저 입력은 숫자를 중복해서 주어지며, n개의 수 중 m개를 뽑아서 출력해야 한다. 예를 들어

4 2
9 7 9 1

이라는 입력이 주어졌을 때, 9 1(첫 번째 9)와 9 1(세 번째 9)는 서로 같기 때문에 이러한 경우를 제외하고 출력을 해야 하는 것이다. 여기서는 중복을 빠르게 캐치할 수 있는 딕셔너리 자료구조나 집합 자료구조를 사용하는 것이 좋다.

B. 코드 분석

전체 코드

import sys
input = sys.stdin.readline
print = sys.stdout.write
n, m = map(int, input().split())

arr = input().split()
arr.sort(key=lambda x: int(x))
dict = {}
ans = []
visited = [False] * n

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

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            ans.append(arr[i])
            solve(cnt + 1)
            visited[i] = False
            ans.pop()

solve(0)

B-1. 준비

import sys
input = sys.stdin.readline
print = sys.stdout.write
n, m = map(int, input().split())

arr = input().split()
arr.sort(key=lambda x: int(x))
dict = {}
ans = []
visited = [False] * n

준비할 것이 많다. 먼저 출력이 많아질 수 있기 때문에 sys 모듈의 sys.stdout.write를 통해서 출력한다. 또한, 사전순으로 출력하기 위해서 arr을 정렬해준다. 여기서는 ''.join()으로 딕셔너리에 저장할 계획이라서 문자열 리스트로 arr로 저장하였다. 이때 정렬의 키로 int()를 사용하여 정렬해준다. 그냥 정렬하게 된다면 사전순으로 정렬되지 않기 때문이다.

ex) arr = ['135', '16', '16'], arr.sort(), arr = ['135', '16', '16']

딕셔너리도 만들고, 출력에 사용할 리스트, 방문 테이블을 설정한다.

B-2. 풀이

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

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            ans.append(arr[i])
            solve(cnt + 1)
            visited[i] = False
            ans.pop()

solve(0)

딕셔너리의 키는 리스트 같은 가변형 자료형은 사용할 수 없기 때문에 문자열을 사용해서 키로 저장해주도록 한다. 그렇기 때문에 cnt == m일 때, ' '.join(ans)를 통해서 딕셔너리의 키를 확인하고 값을 넣어주었다.

또한, sys.stdout.write는 개행문자를 넣어주어야 정상적인 출력 조건을 충족한다.

for 반복문에서는 같은 숫자를 재사용할 수 없기 때문에 방문하지 않은 숫자만 고려하도록 한다.

총평

N과 M 문제가 이렇게 다양하게 출제될 수 있구나...?

자만하지 말고 정직하게 풀자.