99클럽 코테 스터디 6일차 TIL + 해시

오늘의 문제 - 해시

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

입출력 예제

---

내 풀이 및 접근 방식

def solution(clothes):
    answer = 1
    closet = {}
    for cloth in clothes:
        if cloth[1] in closet:
            closet[cloth[1]] += 1
        else:
            closet[cloth[1]] = 1
        
    for value in closet.values():
        answer *= (value+1)
        
    answer -= 1
        
    return answer

 

풀이 방식

1. closet 딕셔너리 생성한 후, 의상의 종류를 key로 하고 의상의 개수를 value로 추가한다.
2. 종류별 의상 개수에 1을 더한 값을 모두 곱한다.
   종류별로 의상을 입는 경우의 수는 종류별 의상 개수+1 이다. ex) 안경, 선글라스, 둘 다 사용 안하는 경우
   종류별 선택 경우의 수를 모두 곱하여 모든 의상 조합의 경우의 수를 구한다.
3. 아무것도 입지 않은 경우의 수를 빼기 위해 answer에서 1을 뺀다.

---

다른 풀이

Counter를 이용하는 풀이

from functools import reduce
from collections import Counter

def solution(clothes):
    counter = Counter([kind for clothe, kind in clothes])

    result = reduce(lambda acc, cur: acc*(cur+1), counter.values(), 1) - 1
    return result
    
# 출처 https://aiday.tistory.com/131

 

풀이 방식

1. 각 의상 종류별로 의상 개수를 저장한 객체를 생성한다.
   ex) counter = Counter({'headgear': 3, 'top': 2, ... })
2. reduce 함수를 이용하여 종류별 의상 개수+1을 곱하여 모두 더한 후 1을 뺀다.

---

회고

공식을 이해하는 것이 중요했던 문제같다. 어제의 문제를 바탕으로 해시를 이용해서 풀이할 수 있었다.

추가로, Counter와 reduce 개념도 익힐 수 있었다.

Counter

Counter 클래스는 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번 나오는지 저장된 객체를 반환한다.
문자열을 인자로 넘길 경우, 각 문자가 몇 번 나오는지 저장된 객체를 반환한다.

해시와 마찬가지로 탐색, 수정 등이 가능하다. ex) counter[key], key in counter 

reduce

reduce는 여러 개의 데이터를 대상으로 누적 집계를 내기 위해 주로 사용한다.
reduce(집계 함수, 순회 가능한 데이터, 초기값)

이 때, 집계 함수는 누적자(accumulator)와 현재값(current value)를 매개변수로 한다.