[프로그래머스][python] Lv.0 - 구슬을 나누는 경우의 수

문제 설명

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수  balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return하는 solution 함수를 완성해주세요.

 

문제를 보자마자 itertools 라이브러리의 combinations 함수를 이용해야겠다고 생각했다. 페이지 내에 제공된 힌트도 조합 공식이었다.

 

Hint
서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다. 

 

작성한 코드 1

from itertools import combinations

def solution(balls, share):
    answer = list(combinations(list(range(balls)), share))
    return len(answer)

 

위와 같은 코드를 작성 후 제출했지만 몇몇 테스트 케이스에서 시간초과로 인해 실패가 떴다 ㅜㅜ

구슬 갯수로 주어진 balls의 값이 커서 리스트로 만든 후 다시 조합 계산을 하는 데 시간이 오래 걸린다고 판단했다.

그래서 그냥 함수 말고 조합 공식을 써보자 하고 다시 코드를 작성했다.

 

작성한 코드 2

import math

def solution(balls, share):
    return math.factorial(balls)/(math.factorial(balls-share)*math.factorial(share))

새로 작성한 코드로 제출하니 말끔히 통과되었다! 조합 계산이 생각보다 시간이 오래걸리나보다ㅠㅠ

 

그리고 다른 분들의 코드를 보다가 발견한 새로운 방법!!

 

math 라이브러리에서 제공하는 comb(n,k) 함수를 사용하는 거다!!

math.comb(n,k) 함수는 nCk와 같은 조합 값을 반환해준다. 

itertools라이브러리의 combinations함수는 매개변수로 리스트를 받는 반면 comb함수는 정수 값을 받기 때문에

처리가 훨씬 빠른 것 같다

 

오늘도 또 하나 배워가는 시간이었다~