문제
코니는 매일 다른 옷을 조합하여 입는 것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음 날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
| 종류 | 이름 |
|---|---|
| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코트 |
- 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
- 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
- 코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
입출력 예
| clothes | return |
|---|---|
| [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] | 5 |
| [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] | 3 |
풀이
설계
- 우선 각 의상 종류마다 의상이 2개씩 존재한다고 가정하고, 의상의 종류에 따라 몇 가지의 조합이 가능한지 생각해 보자.
의상이 A(a, b) 1종일 경우
→ 1개씩 입는 조합 : a, b
→ 총 2개
의상이 A(a, b)와 B(c, d) 2종일 경우
→ 1개씩 입는 조합 : a, b, c, d = 4개
→ 2개씩 입는 조합 : ac, ad, bc, bd = 4개
→ 총 8개
의상이 A(a, b)와 B(c, d), C(e, f) 3종일 경우
→ 1개씩 입는 조합 : a, b, c, d, e, f = 6개
→ 2개씩 입는 조합 : ac, ad, ae, af, bc, bd, be, bf, ce, cf, de, df = 12개
→ 3개씩 입는 조합 : ace, ade, acf, adf, bce, bcf, bde, bdf = 8개
→ 총 26개 - 1을 자세히 보면 각 결괏값이 3-1, (3*3)-1, (3*3*3)-1임을 알 수 있다.
- 만약 의상 종류가 3개라면?
1종일 경우
→ 1개씩 입는 조합 : a, b, c
→ 총 3개
2종일 경우
→ 1개씩 입는 조합 : a, b, c, d, e, f = 6개
→ 2개씩 입는 조합 : ad, ae, af, bd, be, bf, cd, ce, cf = 9개
→ 총 15개
종합하면 4-1, (4*4)-1의 규칙을 보인다. - 2, 3을 종합하면 (A의 종류의 수 + 1)(B의 종류의 수 + 1)...(N의 종류의 수 + 1) - 1의 공식을 유도할 수 있다.
- 따라서 의상의 종류와 각 종류별 개수만 알 수 있다면 계산이 가능하다.
- 빈 딕셔너리를 생성한 후, 주어지는 input에서 의상의 종류에 해당하는 데이터를 key로 하여 해당 키가 존재하지 않을 경우 값을 1로, 해당 키 값이 중복될 경우 value를 1씩 증가시키는 방식으로 의상 종류의 값을 구할 수 있다.
이렇게 구한 딕셔너리의 value에 대하여 4의 공식을 적용하면 된다.
코드
def solution(clothes):
clothes_dict = {}
for i in clothes:
if i[1] in clothes_dict:
clothes_dict[i[1]] += 1
else:
clothes_dict[i[1]] = 1
answer = 1
for _, v in clothes_dict.items():
answer *= (v + 1)
answer -= 1
return answer파이썬이라 당연할 수도 있겠지만, 코드로 해시를 구현하는 것보다 규칙성을 파악하는 게 훨씬 어렵다.
