[Python/파이썬] 백준 15664번 N과 M (10)

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보다 작거나 같은 자연수이다.

출력

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

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

코드

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
s = []


def bt(idx, selected):
    if len(selected) == m:  # 선택된 숫자가 m개
        if selected not in s:   # 아직 출력된 적 없는 수열이라면 출력
            print(*selected)
            s.append(selected)
        return
    if idx+1 < n:
        bt(idx+1, sorted(selected+[arr[idx+1]]))    # idx+1번째 원소 포함 O
        bt(idx+1, selected)                         # idx+1번째 원소 포함 X


bt(-1, [])

 

bt() 함수

• idx+1이 n 미만이라면 idx+1번째 원소를 포함시키는 경우와 포함 안 하는 경우로 나누어 bt함수를 재귀적으로 호출한다.
• 선택된 숫자들 selected의 길이가 m개라면 return할 것인데, 이때 selected가 아직 출력된적 없는 수열이라면 출력한다.

리스트는 unhashable한 타입이기 때문에 집합에 넣을 수 없다. 그렇기 때문에 이미 출력된 수열은 s라는 배열에 넣고 수열을 출력할 때마다 이미 s에 존재하는 수열인지 확인하여 아직 s에 존재하지 않는 수열들만 출력해준다.

 

조합을 이용한 풀이

from itertools import combinations

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))

s = set()
for comb in combinations(arr, m):
    if comb not in s:
        s.add(comb)
        print(*comb)

정렬된 리스트 arr에서 m개의 원소를 뽑아 만들 수 있는 모든 조합 경우의 수를 비내림차순으로 출력한다.

이때 이미 출력된 수열은 다시 출력하지 않기 위해 집합을 이용했다.