난이도 : level 2
유형 : 해시-키
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42578
문제 파악
clothes라는 2차원 배열에 [의상의 이름, 의상의 종류] 순으로 입력을 받습니다.
저는 편의상 [이름,종류] 라고 읽겠습니다.
종류별로 의상을 한가지 착용할 수 있습니다.
어떠한 종류의 의상을 착용하지 않을 수도 있지만
최소한 1개의 의상은 착용해야 합니다.
예시를 보며 흐름을 파악해봅시다.
clothes 배열에
[["a", "hat"], ["b","pants"],["c","hat"]]
이렇게 hat 종류 a,c 두개와 pants 종류 b 한개를 입력 받았다면
return해야 하는 수는 5 입니다.
어떻게 5가지가 나오냐면
a
b
c
a,b
b,c
이렇게 다섯가지가 나옵니다.
처음에는 dictionary 자료형에 value를 리스트로 감싸서 종류별로 옷을 담았습니다.
dict = {
hat : [a,c]
pants : [b]
}그 다음 생각은 for문을 돌면서 i값(선택할 종류 수)에 따라 경우의 수를 세는 방식이었습니다.
i=1 → dict의 key 중 하나를 선택, 해당 요소 개수만큼 count
i=2 → dict의 key 중 두 개를 선택(조합), 선택된 종류들의 개수를 곱해서 count
조금더 복잡한 예시를 보고 싶어서 top 리스트를 추가해봤습니다.
dict = {
hat : [a,c],
pants : [b],
top : [d,e,f]
}
i=1 → hat 2 + pants 1 + top 3 = 6
i=2 → hat×pants(2×1=2) + hat×top(2×3=6) + pants×top(1×3=3) = 11
i=3 → hat×pants×top = 2×1×3 = 6
총합 = 23
→ 이런 식으로 조합을 직접 돌려도 답은 구할 수 있습니다.
하지만 코드가 장황해지고 경우의 수를 빼먹지 않으려면 꽤 까다롭습니다.
여기서 깨달은 점은, 입은 것을 일일이 세는것보다 전체 경우의수에서 전부 안입은 경우의 수 한가지를 빼면 답을 구할 수 있다는 것입니다.
hat → 2개 + 안 입기(1) = 3
pants → 1개 + 안 입기(1) = 2
top → 3개 + 안 입기(1) = 4
전체 경우의 수 = 3 × 2 × 4 = 24
여기서 전부 안 입기(1가지)를 제외하면 24 - 1 = 23
해답 및 풀이
def solution(clothes):
# 1) 종류별 개수 세기
kind_count = {} # 종류 개수
for name, kind in clothes:
# kind 키가 이미 있으면 +1, 없으면 0에서 시작해 +1
kind_count[kind] = kind_count.get(kind, 0) + 1
# 2) 곱셈 원리 적용
answer = 1
for cnt in kind_count.values():
answer *= (cnt + 1) # "안 입기(1)" 선택지를 포함해서 (cnt + 1)을 곱해줌
return answer - 1 # 다 안입은 경우의수 1가지를 빼줌
