문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1예제 출력 1
1
2
3예제 입력 2
4 2예제 출력 2
1 2
1 3
1 4
2 3
2 4
3 4예제 입력 3
4 4예제 출력 3
1 2 3 4최종 코드
from itertools import combinations
# 입력 처리
N, M = map(int, input().split())
# 1부터 N까지의 숫자 리스트
numbers = list(range(1, N + 1))
# M개를 고른 조합 생성
combs = combinations(numbers, M)
# 결과 출력
for comb in combs:
result=' '.join(map(str, comb))
print(result)오늘 푼 N, M(1)과 다르게 모든 중복 수열을 제외한 순열을 생성하는게 아닌, 순서 상관없이 겹치는 내용을 뺀 모든 조합을 생성하는 문제이다.
- combinations를 사용하면 조합 즉(1,2),(2,1)은 중복된다 간주하여 남은 수열을 만들어 주는 라이브러리
permutations와 비교해보자!!
itertools.permutations
- 리스트에서 모든 가능한 순열 생성, 요소의 순서가 중요하며 모든 가능한 순서 포함
itertools.combinations
- 리스트에서 지정된 길이의 조합 생성, 조합은 순서 중요하지 않고, 선택된 요소 순서와는 상관없이 모든 가능한 조합 포함
근데, 다음부터 combinations가 어떤 활용도가 있는지 인지해서 푸는것도 좋은 방법이지만 재귀 함수로 풀 수도있다고 해서 참고해보려한다.
N, M = map(int, input().split())
def combinations(N, M, start=1, numbers=[]):
if len(numbers) == M:
result = ' '.join(map(str, numbers))
print(result)
return
for i in range(start, N+1):
combinations(N, M, i+1, numbers+[i])
combinations(N, M)진짜 계속 이렇게 보면서 푸는게 도움이 될까 싶을 정도로 이게 언제쯤 내머리속에서 구상되서 구현화될지 감이 안잡히지만.. 쨋든 분석해보면
함수 combinations는 N,M을 인자로 받고 start 넘버 1 세팅, numbers 빈 리스트 세팅을 해준다
그 후 numbers의 길이가 M과 같다면
그 안에는 (내일 다시)
웹 개발자 되고 시포용