[Python/DFS,백트래킹] 15655 N과 M(6)

문제

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

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

 

입력

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

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

출력

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

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

 

입력 예시	출력 예시
3 1 4 5 2	2 4 5
4 2 9 8 7 1	1 7 1 8 1 9 7 8 7 9 8 9
4 4 1231 1232 1233 1234	1231 1232 1233 1234

---

 풀이

1. dfs 사용

def dfs(start):
    if len(temp) == m:
        print(*temp)
        return
    for i in range(start, n):
        if arr[i] not in temp:
            temp.append(arr[i])
            dfs(i + 1)
            temp.pop()

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
temp = [] # 나올 수 있는 combination 만들면서 값을 담는 list 
dfs(0) # start 번째 index의 값으로 시작하는 combination 생성

 

 

 

2. itertools의 combinations 사용

문제) print(i) 하면 괄호가 같이 출력됨

for i in combinations(arr, m):
    print(i)
'''
(1, 7)
(1, 8)
(1, 9)
(7, 8)
(7, 9)
(8, 9)
'''

 

 

해결 1) join 함수 사용

from itertools import combinations

n, m = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort() #***** 오름차순으로 print하기 위해 정렬 먼저*****

for i in combinations(arr, m):
    print(' '.join(map(str, i)))

join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수

a = ['1', '2', '3']
print(' '.join(a))
# 1 2 3

b = [1,2,3]
print(' '.join(map(str,b)))
# 1 2 3

해결 2) print(*i)

from itertools import combinations

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

for i in combinations(arr, m):
    print(*i)