문제
https://school.programmers.co.kr/learn/courses/30/lessons/42578
코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.
- 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
- 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
- 코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
입출력 예
나의 풀이 (실패)
def solution(clothes):
answer = 1
dict = {}
for name, type in clothes:
if type not in dict:
dict[type] = []
dict[type].append(name)
for type in dict:
answer *= len(dict[type])
if len(dict) > 1:
answer += len(clothes)
return answer- 타입의 개수를 유동적으로 선택해서 입을 수 있다는 것을 간과했다. 예를 들면 세 가지 타입이 있을 때 두 가지의 타입만 선택하는 경우의 수를 고려하지 못했다.
다른 사람의 풀이
def solution(clothes):
dict = {}
for name, type in clothes:
if type not in dict:
dict[type] = [name]
else:
dict[type] += [name]
answer = 1
for _, value in dict.items():
answer *= (len(value) + 1)
return answer - 1딕셔너리에 의상을 종류별로 그룹화해서 저장한다.
이 딕셔너리 값의 길이, 즉 옷의 종류별 개수를 이용해 답을 구할 것이다.
A의 종류가 N개, B의 종류가 M개일 때 전체 경우의 수는 (N+1)(M+1)로 구할 수 있다.
이 식을 전개해서 보면 이해하기가 더 쉽다.
`(N+1)(M+1) = NM + N + M + 1`
N과 M을 모두 착용하는 경우, N만 착용하는 경우, M만 착용하는 경우, 아무것도 착용하지 않는 경우의 수를 더한 것이다.
만약에 옷의 종류가 세 가지라서 여기에 하나를 더 더한다면?
`(NM + N + M + 1)(K+1) = NMK + NK + MK + K + NM + N + M + 1`
N, M, K 세 가지 옷의 종류에 대해
세 가지를 모두 입는 경우, 두 가지만 입는 경우, 한 가지만 입는 경우를 모두 계산할 수 있다.
최종적으로 답을 출력할 때는 아무것도 착용하지 않는 경우의 수를 제외하기 위해 `answer-1`을 한다.