[Programmers] 구슬을 나누는 경우 (Python) (feat.ChatGPT)

코딩 1일 1문제! 오늘의 문제는 프로그래머스의 구슬을 나누는 경우 입니다.

프로그래머스

👨🏻‍💻 문제 풀이 - SOMJANG

$$\frac{n!}{(n-m)! \times (m!)}$$

힌트에 적혀있는 경우의 수 공식을 활용하였습니다.

👨🏻‍💻 코드 (Solution)- SOMJANG

import math


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

👨🏻‍💻 문제 풀이 - ChatGPT

해당 문제는 주어진 balls 개수 중에서 share 개의 구슬을 고르는 경우의 수를 구하는 문제입니다.

구슬을 고르는 순서는 고려하지 않으므로, 주어진 balls개의 구슬 중 share개를 고르는 경우의 수는 서로 다른 n개 중 m개를 뽑는 경우의 수 공식을 사용하여 구할 수 있습니다. 이 때, n = balls, m = share 이며, n! / (n-m)! x m! 공식을 이용하면 됩니다.

따라서, 아래와 같은 코드로 문제를 해결할 수 있습니다.

👨🏻‍💻 코드 (Solution) - ChatGPT

import math

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

위 코드에서 math 모듈의 factorial 함수를 이용하여 주어진 balls와 share 값에 대한 경우의 수를 계산하고, 계산 결과를 반환합니다. 주의해야 할 점은, 계산 결과가 매우 커질 수 있으므로, 계산 시 overflow가 발생하지 않도록 하기 위해 나눗셈 연산을 // 연산자를 이용하여 처리해야 합니다.

저와 같은 방식으로 풀어서 정말 놀랐습니다.

👨🏻‍💻 문제 풀이 - ChatGPT - 공식을 사용하지 않고 풀 수 있을까?

재귀함수를 이용하여 모든 경우를 탐색하고, 선택된 구슬의 개수가 share와 같아지면 경우의 수를 증가시키고, 재귀적으로 호출하며 모든 경우를 찾습니다. 중복을 제거하지 않고 경우의 수를 반환합니다.

위 코드를 실행하면, 예상한 결과가 나오게 됩니다. balls가 3이고 share가 2인 경우에는 3이 나오고, balls가 5이고 share가 3인 경우에는 10이 나오게 됩니다.

👨🏻‍💻 문제 풀이 - ChatGPT - 공식을 사용하지 않고 풀 수 있을까? - 시간 초과 경우 존재

def solution(balls, share):
    cnt = 0
    
    def pick_ball(pos, selected):
        nonlocal cnt
        if selected == share:
            cnt += 1
            return
        for i in range(pos, balls):
            pick_ball(i + 1, selected + 1)
    
    pick_ball(0, 0)
    return cnt

특정 테스트 케이스에서 시간초과가 발생하였고 많은 케이스에서 오랜 시간이 걸렸습니다.

확실히 힌트에서 알려준 공식을 활용한 방법과 차이가 많이 났습니다.

 

이후에도 공식을 사용하지 않고 푸는 방법을 수차례 요구하였으나

틀린 답변이거나 위와 같이 시간초과가 발생하는 코드였습니다.

 

읽어주셔서 감사합니다.

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07