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

백준 15664 - N과 M(10)

시간 제한 1초, 메모리 제한 512MB

# 조건

• N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 비내림차순이어야 한다.
    • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 수가 주어진다.
• 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

# 접근 방법

• 조합과 SET을 활용하거나, 백트래킹을 이용하여 풀 수 있다.
• python의 itertools 모듈을 들고와서 combination을 사용해준다.
• 우선 사전 순 조합을 만들기 위하여 입력받은 nums를 정렬해준다.
• M크기의 조합을 만들건데 set형태로 받아주어 중복된 결과들을 지워주고 출력하면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  

N, M = map(int, input().split())  
nums = [*map(int, input().split())]  
nums.sort()  
result = sorted(set(combinations(nums, M)))  
for i in result:  
    print(*i)

• 위 답안을 백트래킹으로 구현해보면 아래와 같다.
• 또한, list의 경우 변경가능한 데이터 유형이기 때문에 변경 불가능하거나 해시할 수 있는 객체가 아니라 바로 set에 들어갈 수 없다.
  • tuple로 변경 후 set에 넣어주면 된다

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def back_tracking(idx, temp):  
    if len(temp) == M:  
        if not tuple(temp) in result:  
            print(*temp)  
            result.add(tuple(temp))  
    for i in range(idx, N):  
        temp.append(nums[i])  
        back_tracking(i+1, temp)  
        temp.pop()  

N, M = map(int, input().split())  
nums = [*map(int, input().split())]  
nums.sort()  

result = set()  
back_tracking(0, [])