[프로그래머스] 의상

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

프로그래머스

 

✍️ 문제 요약

- `clothes` 배열을 통해 코니가 가진 아이템(=의상)의 [이름, 종류]이 주어진다.

- 예를 들어, `clothes = [["A", "headgear"], ["B", "headgear"], ["C", "eyewear"], ["D", "eyewear"]]` 이라면 서로 다른 두 종류의 headgear와 eyewear를 가지고 있는 것이다.

- 같은 종류의 아이템은 하나만 착용할 수 있다.

    - `A`와 `B`는 동시에 착용할 수 없다.

- 착용한 아이템의 일부가 겹치더라도, 다른 아이템이 겹치지 않거나 추가 아이템을 착용한 경우에는 서로 다른 방법으로 계산한다.

    - 예를 들어, `A` 와 `A, C`는 다른 방법인 것이다.

- 서로 다른 방법의 조합의 수를 반환하라.

 

🤔 접근법

이해가 쉽도록 예시로 접근했다.

만약 ``clothes = [["A", "headgear"], ["B", "eyewear"], ["C", "eyewear"], ["D", "face"], ["E", "face"], ["F", "face"]]` 이라면, 의상 종류(headgear, eyewear, face)의 수는 3개이므로 모든 조합은 의상을 1 ~ 3개 선택할 때에서 나온다.

 

1) 의상을 1개 선택할 때

['headgear'] 선택 -> 1가지

['eyewear'] 선택 -> 2가지

['face'] 선택 -> 3가지

➡️ 이때 경우의 수는 6(=1+2+3)가지

 

2) 의상을 2개 선택할 때

['headgear', 'eyewear'] 선택 -> 1 * 2 = 2가지

['headgear', 'face'] 선택 -> 1 * 3 = 3가지

['eyewear', 'face']선택 -> 2 * 3 = 6가지

➡️ 이때 경우의 수는 11(=2+3+6)가지

 

3) 의상을 3개 선택할 때

['headgear', 'eyewear', 'face'] 선택 -> 1 * 2 * 3 = 6가지

➡️ 이때 경우의 수는 6가지

 

따라서 총 경우의 수는 23(=6+11+6)가지이다.

 

즉, 의상의 종류가 n개 있을 때 그 중 1개부터 n개까지 선택한다.
그리고 선택한 각각의 조합에 대해서 경우의 수를 구한뒤 이를 누적하여 정답을 구한다. 

 

💪 무식하게 풀기

의상의 종류를 key로 가지면서 이름 리스트를 value로 가지는 `dic` 딕셔너리를 이용한다.

예를 들어, `clothes = [["A", "headgear"], ["B", "eyewear"], ["C", "eyewear"], ["D", "face"], ["E", "face"], ["F", "face"]]` 이라면,

`dic`에는 `{'headgear': ['A'], 'eyewear': ['B', 'C'], 'face': ['D', 'E', 'F']}`가 저장되는 것이다.

 

이제 반복문이 총 3개가 등장한다. 등장 순서대로 위 예시에 빗대어 설명하자면,

첫 번째 for문: 3가지 종류의 의상(headgear, eyewear, face) 중에서 몇(=`i`) 가지 의상을 입을지 "개수" 선택

두 번째 for문: `i`개의 의상을 입어야 할 때, 전체 의상 "종류" 중에서 `i`개의 조합 선택

마지막 for문: 선택된 `i`개의 조합에서 의상의 "이름"에 따라 나올 수 있는 경우의 수 계산

from collections import defaultdict
from itertools import combinations

def solution(clothes):
    dic = defaultdict(list)
    for name, ty in clothes: # 의상 이름, 종류
        dic[ty].append(name)
        
    res = 0
    for i in range(1, len(dic)+1):
        for x in combinations(dic.keys(), i): # 3P1, 3P2, 3P3
            tmp = 1 # 가진 아이템 중 i개 골랐을 때 조합 수
            for item in x:
                tmp *= len(dic[item]) # 한 조합에 뽑힌 요소끼리 곱셈
            res += tmp
    
    return res

생각나는대로 무식하게 푼 풀이이다보니 삼중 반복문이 나오고 말았다..😱

채점 결과, 시간 초과로 한 개의 테스트를 통과하지 못했다.

이를 최적화해보자❗️

 

🎯 최적화

위에서 사용한 예시와 동일하게 `{'headgear': ['A'], 'eyewear': ['B', 'C'], 'face': ['D', 'E', 'F']}`이 있다고 할 때,

의상의 조합을 크게 보면 headgear X eyewear X face 의 조합이다.

 

각 가지수를 생각했을 때,

headgear는 ('A' 1가지) + (headgear 착용 안하는 경우 1가지) = 총 2가지

eyewear는 ('B', 'C' 2가지) + (eyewear 착용 안하는 경우 1가지) = 총 3가지

face는 ('D', 'E', 'F' 3가지) + (face 착용 안하는 경우 1가지) = 총 4가지

 

따라서 headgear X eyewear X face 의 조합의 수는 2 * 3 * 4 = 24가지이다.

 

⚠️ 문제에서 "하루에 최소 한 개의 의상은 입는다."는 조건이 있기 때문에,

위 조합에서 (headgear 착용 안하는 경우) X (eyewear 착용 안하는 경우) X (face 착용 안하는 경우) = 1가지를 제외한다.

 

따라서 위 예제에서 답은 24 - 1 = 23가지이다.

즉, `(headgear 수 + 1) * (eyewear 수 + 1) * (face 수 + 1) - 1` 의 공식으로 해결 가능하다.

 

from collections import defaultdict
def solution(clothes):
    dic = defaultdict(list)
    for name, tpe in clothes:
        dic[tpe].append(name)
    
    res = 1
    for x in dic.values():
        res *= (len(x) + 1)
    
    return res - 1

온전히 혼자 생각해낸 풀이라 뿌듯했다. 😋

 

👀 다른 사람의 코드를 탐구해보기

해결 방법은 같으나 다르게 구현한 풀이이다.

나는 각 의상의 종류에 따른 이름을 리스트로 저장했으나, 아래 풀이는 각 의상의 종류를 누적하며 카운트만 한다.

문제를 해결하기 위해서는, 종류에 따른 의상의 "개수"만 필요하기 때문에 효율적인 풀이라고 생각한다.

def solution(clothes):
    dic = dict() # 특정 종류 의상의 개수를 담을 딕셔너리
    for name, tpe in clothes:
        dic[tpe] = dic.get(tpe, 0) + 1
    
    res = 1
    for x in dic.values():
        res *= (x + 1)
    
    return res - 1

 

📚 참고 자료

https://aiday.tistory.com/131