[Python] 프로그래머스 - 의상

1. 문제정보

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

2. 풀이

조합을 이용한 풀이를 우선으로 생각했다. 주어진 의상의 종류가 n가지일 때 리스트에 담고 1개씩 입을 때, 2개씩 입을 때...n개씩 입을 때 모든 조합을 구한 후 종류별 의상의 수를 가지고 전체 경우의 수를 계산하였다. 하지만 결과는 일부 케이스에서 시간초과가 발생했다.

 

다른 분들의 풀이를 보니 경우의 수를 이용하여 해결한 분들이 많았다. 예를들어 A종류 3개, B종류 2개, C종류 2개가 있을 때 종류별로 최소 1개씩(A 중 1개 선택, B 중 1개 선택, C 중 1개 선택) 착용해야 할 때 경우의 수는 3 x 2 x 2로 총 12가지이다. 하지만 문제의 조건은 종류별로 꼭 1개씩 입지 않아도 된다고하니 경우의 수를 구할 때 입지 않는 경우의 수를 추가해야 한다. 즉 (3+1) x (2+1) x (2+1)로 36가지인데 이 때 전부 입지 않는 경우(1가지)를 빼야해서 정답인 35를 구할 수 있다.

 

3. 소스코드

- 시간초과 소스코드

def comb(arr, n):
    result = []
    if n == 0:
        return [[]]
    elif n == 1:
        return [[i] for i in arr]
    elif n >= 2:
        for i in range(len(arr)):
            el = arr[i]
            p = comb(arr[i+1:], n-1)
            for rest in p:
                result.append([el]+rest)
    return result

def solution(clothes):
    clothMap = {}
    for name, ty in clothes:
        if clothMap.get(ty) == None:
            clothMap[ty] = 1
        else:
            clothMap[ty] += 1
            
    answer = 0
    types = list(clothMap.values())
    for i in range(1, len(types)+1):
        # 각 의상의 수로 조합을 구함 => 각 조합의 원소를 곱한 후 모두 더하면 전체 경우의 수가 나옴
        results = comb(types, i)
        for result in results:
            cnt = 1
            for r in result:
                cnt *= r
            answer += cnt
    return answer

 

- 성공한 소스코드

def solution(clothes):
    # 의상별 수를 dictionary에 저장
    clothMap = {}
    for name, ty in clothes:
        if clothMap.get(ty) == None:
            clothMap[ty] = 1
        else:
            clothMap[ty] += 1

    # 경우의 수 계산, +1을 하는 경우는 입지 않았을 때의 경우
    answer = 1
    types = list(clothMap.values())
    for cnt in types:
        answer = answer * (cnt+1)
    
    # -1을 하는 이유는 의상을 모두 입지않은 경우제외
    return answer-1

 

배운 점

조합을 이용한 풀이(모든 경우의 수를 구한 후 직접계산)가 시간초과가 발생했을 때 수학적인 관점으로 해결할 수 있는지 고민해볼 수 있을 것 같다. 문제를 수학적인 풀이로 바라볼 수 있는 관점을 배울 수 있었던 것 같다.