백준 알고리즘 No.15649 N과 M (1)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
체감 난이도: ★
지난 스터디에서 블랙잭 문제를 combinations 함수로 푸신 분이 있어서 파이썬의 순열 & 조합 함수의 존재를 알게되었다. 그래서 조합 함수를 활용해봤더니 바로 풀렸다.^^
Code
from itertools import permutations
n, m = map(int, input().split())
n_list = [i+1 for i in range(n)]
per = permutations(n_list, m) # 순열 함수 사용
for result in per:
print(*result) # 언패킹한 데이터 출력
Solution
N과 M을 입력받은 다음, 1~N까지의 값으로 이루어진 n_list를 만들어준다. 그리고 순열 함수를 활용해 조건을 만족하는 수열을 모두 출력한다.
✔ 조합형 Iterator 함수
itertools모듈에서 함수를 import 해줘야 함!!
product(*iterables, repeat = 1)
여러 iterable의 데카르트 곱을 반환하는 함수
from itertools import product
data = [1, 2, 3]
result = list(product(data, repeat=2))
print(result)
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
permutations(iterable, r)
주어진 iterable에서 길이가 r인 모든 순열을 생성하는 함수
from itertools import permutations
data = [1, 2, 3]
result = list(permutations(data, 2))
print(result)
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
combinations(iterable, r)
주어진 iterable에서 길이가 r인 모든 조합을 생성하는 함수
from itertools import combinations
data = [1, 2, 3]
result = list(combinations(data, 2))
print(result)
[(1, 2), (1, 3), (2, 3)]
combinations_with_replacement(iterable, r)
주어진 iterable에서 길이가 r인 모든 조합을 중복을 허용하여 생성하는 함수
from itertools import combinations_with_replacement
data = [1, 2, 3]
result = list(combinations_with_replacement(data, 2))
print(result)
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃
