[백준] 15650 - N과 M (2) (파이썬, Python)

[문제 출처]

www.acmicpc.net/problem/15650

15650번: N과 M (2)

---

이 문제는 조합을 이용하면 해결이 되는 문제입니다!

 

조합을 직접 구현해 본 적이 없어 이 문제를 만남 김에 구현을 해보았습니다~!

 

전체 코드

import sys

def combination(data, n):
    res = []
    
    if n == 1:
        return [ [e] for e in data ]

    for idx in range(len(data)-1):
        rest = data[idx+1:]

        restCombination = combination(rest, n-1)
        
        res.extend([ [ data[idx] ] + comb for comb in restCombination])

    return res

N, M = map(int, sys.stdin.readline().strip().split())

data = [ str(i) for i in range(1, N+1)]

res = combination(data, M)

for item in res:
    print(" ".join(item))

 

---

직접 구현을 해보았지만 Python에는 이미 combination 라이브러리가 제공되고 있으므로

라이브러리를 이용해서도 풀이를 해보았습니다!

 

코드는 아래와 같습니다😊

 

코드

from itertools import combinations
import sys

N, M = map(int, sys.stdin.readline().strip().split())

data = [ str(e) for e in range(1, N+1) ]

res = list(combinations(data, M))

for item in res:
    print(" ".join(item))

 

확실히 코드가 간결해졌습니다!

또한 시간을 확인해보니 제 코드 기준으로는 아래와 같은 차이를 보였습니다.

 

 

- 직접 구현한 코드: 72ms

- 라이브러리를 이용한 코드: 64ms

 

실전 코딩 테스트 문제에서 조합 문제를 만나면 라이브러리를 이용하는 게 좋을 거 같아요😁