백준15655 / 파이썬 / N과 M(6)

N과 M (6)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

예제 입력 1 복사

3 1
4 5 2

예제 출력 1 복사

2
4
5

예제 입력 2 복사

4 2
9 8 7 1

예제 출력 2 복사

1 7
1 8
1 9
7 8
7 9
8 9

예제 입력 3 복사

4 4
1231 1232 1233 1234

예제 출력 3 복사

1231 1232 1233 1234

정답 코드)

def c(arr, m, start=0, current_arr=[]):

    if len(current_arr) == m:  # 원하는 길이의 조합을 만들었을 때

        print(' '.join(map(str, current_arr)))

        return

    for i in range(start, len(arr)):

        # 현재 원소를 추가하고, 그 다음 원소를 찾기 위해 재귀 호출

        c(arr, m, i + 1, current_arr + [arr[i]])

n, m = map(int, input().split())

num = list(map(int, input().split()))

num.sort()

c(num, m)

문제 풀이)

1.중복을 허용하지 않고 오름차순으로 수열을 출력하기 때문에 처음 배열을 오름차순으로 정렬한 뒤 재귀함수를 구현했다.

2.for문을 돌면서 arr의 원소들을 추가하고, 다음 요소를 선택하기 위해 재귀 호출을 한다. 이때 start 인덱스를 i + 1로 주어 중복된 조합을 방지한다.

3. 종료조건에 m(수열의 길이)과 같게 되면 이를 출력하고 재귀를 종료하여 조합이 완성될때 마다 출력한다.