문제 설명
코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.
코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
풀이 00
def solution(clothes):
# 빈 딕셔너리 생성
hash_map = {}
# clothes를 categry별로 그룹화
for name, category in clothes:
if category not in hash_map:
hash_map[category] = [] # 카테고리 키(key)에 대해 빈 리스트 초기화
hash_map[category].append(name) # 이름 (value) 추가
answer = 1
for key, value in hash_map.items():
answer *= (len(value) + 1)
return answer - 1맨 처음으로 카테고리별 옷의 종류를 담아두도록 한다. 다음은 key, value로 각각 카테고리, 옷을 딕셔너리에 담도록 하는 코드이다.
# clothes = [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
# 01
# 빈 딕셔너리 생성
hash_map = {}
# 의류를 종류별로 그룹화
for name, category in clothes:
if category not in hash_map:
hash_map[category] = [] # 카테고리 키(key)에 대해 빈 리스트 초기화
hash_map[category].append(name) # 이름 (value) 추가
# 02
hash_map = {}
for name, category in clothes:
if category not in hash_map.keys():
hash_map[category] = [name]
else:
hash_map[category] += [name]
# 03
from collections import defaultdict
# defaultdict를 사용해 종류별로 의상 이름 그룹화
hash_map = defaultdict(list)
for name, category in clothes:
hash_map[category].append(name)
# defaultdict를 일반 딕셔너리로 변환
result = dict(hash_map)
>>> {'headgear': ['yellow_hat', 'green_turban'], 'eyewear': ['blue_sunglasses']}위와 같이 딕셔너리로 만든 이후, value로 들어간 list의 길이를 (n+1)(m+1) 식에 맞춰 answer *= (len(value) + 1)로 코드를 작성해 준다. 이후, -1을 해주는데 이 경우는 아무것도 착용하지 않은 것을 제외하기 위함이다.
풀이 01
- Counter
from collections import Counter
def solution(clothes):
# 카테고리별 의상 개수 구하기
counter = Counter([category for name, category in clothes])
# 경우의 수 계산
answer = 1
for count in counter.values():
answer *= (count + 1) # 각 카테고리에서 선택하지 않는 경우 포함
# 아무것도 선택하지 않는 경우 제외
return answer - 1풀이 00과 달리 Counter를 사용하여 카테고리별 의상 개수를 구하고, 이를 활용하여 의상 개수인 values값을 가지고 오도록 하여 answer를 구하도록 했다.
풀이 02
from collections import Counter
from functools import reduce
def solution(clothes):
# 카테고리별 Counter 구하기
counter = Counter([category for name, category in clothes])
# 경우의 수 계산
answer = reduce(lambda acc, cur: acc*(cur+1), counter.values(), 1) - 1
return answer풀이 01번은 for loop를 사용하여 누적 곱을 구하고 있는데 reduce를 사용하면 더욱 간편한 풀이가 가능하다.
- reduce(function, iterable[, initializer])
- function: 두 개의 인자를 받아 누적 작업을 수행하는 함수
- iterable: 반복 가능한 객체 (예: 리스트, 튜플 등)
- initializer (선택): 누적 작업의 초기값. 생략하면 iterable의 첫 번째 요소가 초기값으로 사용
- 리스트나 다른 반복 가능한 객체의 모든 요소를 누적해서 하나의 값으로 계산하는 함수
- 모든 카테고리의 경우의 수를 곱해서 전체 조합을 계산하는 역할
from functools import reduce
# 누적 곱 계산
numbers = [2, 3, 4]
result = reduce(lambda acc, cur: acc * cur, numbers, 1) # 초기값: 1
print(result) # 출력: 24 (2 * 3 * 4)
>>>
동작 원리
초기값: acc = 1
첫 번째 값: cur = 2 → acc = 1 × 2 = 2
두 번째 값: cur = 3 → acc = 2 × 3 = 6
세 번째 값: cur = 4 → acc = 6 × 4 = 24 answer 부분을 천천히 살펴보자.
- function (첫 번째 인자)
- lambda acc, cur: acc * (cur + 1)로 정의된 익명 함수
- acc: 누적된 결과값(초기값은 initializer에서 설정됨).
- cur: iterable에서 현재 처리 중인 값.
- iterable (두 번째 인자)
- counter.values(): 각 카테고리별 의상 개수
- initializer (세 번째 인자): 1
- 누적 계산의 초기값
- 첫 번째 cur 값과 계산을 시작하기 전에 누적값 acc가 1로 설정
동작 과정은 다음과 같다.
lambda acc, cur: acc * (cur + 1)로 계산
- 초기값: acc = 1
- 첫 번째 값: cur = 2 ("headgear"의 의상 수)
- acc = acc × (cur + 1) = 1 × (2 + 1) = 3
- 두 번째 값: cur = 1 ("eyewear"의 의상 수)
- acc = acc × (cur + 1) = 3 × (1 + 1) = 6
- 결과: 6 − 1 = 5 (아무것도 선택하지 않는 경우 제외)
비슷한 문제
import sys
# 테스트케이스 개수
T = int(sys.stdin.readline().strip())
for _ in range(T):
hash_map = {}
# 의상 개수
n = int(sys.stdin.readline().strip())
for _ in range(n):
# 의상과 카테고리
name, category = sys.stdin.readline().strip().split()
# 카테고리별 의상 그룹화
if category not in hash_map:
hash_map[category] = []
hash_map[category].append(name)
# 모든 경우의 수 계산
answer = 1
for key, value in hash_map.items():
answer *= (len(value) + 1)
# 아무것도 입지 않는 경우 제외 후 출력
print(answer - 1)
참고
