프로그래머스 | 해시 - 의상 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=python3

프로그래머스

 

🔅 문제 접근

- 문제 및 제한사항을 확인해보니 조합을 활용하여 겹치는 것이 없이 코디의 경우의 수를 세면 될 것 같다는 생각이 들었다. 일단 코디에 사용할 카테고리를 정하고, 그 안에서 어떤 옷을 입을지 계산하는 방식으로 알고리즘을 구성하였다.

 

  (1) 코디에 사용하는 카테고리의 개수가 1개일때, 2개일때, n개일때 각각 카테고리 선정에 대한 조합을 구하고

  (2) 해당 조합일때에 해당되는 옷의 개수를 전부 곱하여서 더하는 방식으로 알고리즘을 구현하였다.

 

🔅 1차 풀이

from itertools import combinations as comb
from math import prod

def solution(clothes):
    answer = 0
    
    d = {}
    counts = []
    
    # 카테고리별 옷 개수를 세기 위하여 dictionary를 이용
    for item, category in clothes:
        if d.get(category) is not None:
            d[category].append(item)
        else:
            d[category] = [item]
            
    # 연산이 간편하도록 최종 옷 개수만 일차원 배열에 정리
    for key, item in d.items():
        counts.append(len(item))
        
    c_num = len(counts)
        
    # 카테고리 조합 생성 뒤, 각 조합의 옷 개수를 모두 곱하여 정답 구하기
    for i in range(1, c_num+1):
        for c in comb(counts, i) : 
            answer += prod(c)
    
    return answer

 

상단과 같이 코드를 작성하였으나, 결과는 1번에서 시간 초과

 

문제의 제한 조건을 다시 보면서 시간초과가 나는 이유를 분석해보았다.

 

<제한조건>

1. 의상의 수는 1개 이상 30개 이하 -> 카테고리의 최대 개수는 30개

2. clothes 문자열의 길이는 1이상 20이하

 

일단, dictionary에서 키 값에 접근하는 시간복잡도는 일반적으로 O(1)이며, 문자열의 길이에 따른 차이는 없다.

따라서 2번 조건인 clotes 문자열에 관한 내용은 크게 고려하지 않아도 되기 때문에 1번 조건을 중점적으로 알아보도록 한다.

 

<edge 케이스 가정>

각 알고리즘의 시간복잡도를 알아본 뒤, edge 케이스에서 연산이 얼마나 발생하는지를 알아보는 식으로 시간초과의 원인을 찾아보겠다.

 

 (1 ) combination 함수의 시간 복잡도 : O(2^n) 

 (2) prod 함수의 시간 복잡도 : O(n)

 (3) for 문의 시간복잡도 : O(n)

 

Big-O 표기법에 따른 계산 : O(2^n * m * n) (n은 카테고리의 개수, m은 의상의 개수)

 

- 의상의 카테고리는 30개이고, 의상의 수는 각 하나씩 있을 때

 - 해당 경우, 최대 연산 횟수는 2^30 * 1 * 30이다. 해당 경우 연산 횟수는 32,212,254,720 (약 300억번)으로 매우 많다. 따라서 해당 경우 시간초과가 발생한다는 점을 알 수 있다.

 

🔅 2차 풀이

GPT의 도움과 다른 여러 풀이를 참고했을때, 내 풀이를 단순화할 수 있는 인사이트를 얻었다.

 

조합을 실제로 나열하는 것이 아니라 개수를 세는 것이기 때문에, 굳이 조합을 하나씩 세서 더할 필요가 없다.

수학적으로 경우의 수를 계산하여 보다 식을 단순화할 수 있다.

 

안경 : 선글라스, 뿔테 안경    -> 선글라스 or 뿔테안경 or X       3가지

아우터 : 가죽자켓                 -> 가죽자켓 or X                          2가지

상의 : 니트, 맨투맨               -> 니트 or 맨투맨 or X                 3가지

 

총 경우의 수 = 3 * 2 * 2 -1 (아무것도 입지 않는 경우의 수 제외)

 

이런 식으로 각 카테고리의 옷을 아무것도 입지 않는 경우를 경우의 수에 포함시킴으로써 조합으로 카테고리를 선택하지 않아도 간단하게 모든 카테고리 조합 경우의 수를 포함하여 값을 구할 수 있다.

 

코드는 다음과 같다.

from itertools import combinations as comb
from math import prod

def solution(clothes):
    answer = 1
    
    d = {}
    
    for item, category in clothes:
        if d.get(category) is not None:
            d[category] += 1
        else:
            d[category] = 1
            
    
    for item in d.values():
        answer *= (item + 1)
    
    answer -= 1
    
    return answer

 

🔅 느낀점 및 배운점

 브루트포스적으로 접근하고 문제를 풀 때가 많은데, 항상 효율성을 생각해야 하므로 답을 구하기 위해 필요한 과정에 집중하고, 답을 구하는데 굳이 필요하지 않은 것 (횟수를 구하면 되는데 모든 항목을 다 구한 다음 센다던지)은 하지 않아도 되면 되도록 피하자.

 

 그리고 조합의 경우 숫자가 조금만 커져도 금방 시간초과가 나기 때문에, 문제를 푸는 방법이 도저히 생각나지 않는 경우나 최댓값이 정말 적어서 써도 괜찮은 경우를 제외하면, 일단 다른 해결법을 먼저 시도해보자. 조합은 최후의 수단으로 여기는 것이 좋을 것 같다.