📍문제

[프로그래머스] Lv.2 위장

📍풀이

• 처음에 itertools로 combinations 불러와서 조합의 개수를 구하려다가 이렇게 간단하게 해결 될 문제가 아닌 것 같아서 defaultdict를 사용하는 방법을 찾았다.
• 입력예시를 보면
  [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]에서 headgear, eyewear의 개수를 세주기 위해 defaultdict를 사용했다.
• 옷의 종류를 key로 가지고, 그 개수를 value로 가지게 한다.

중요한 포인트

개수를 구할 때 규칙을 찾는 것이 중요하다.
첫번째 입력 예시에서, 이를 defaultdict로 만들고 개수를 value로 가지게 하면 {'headgear': 2, 'eyewear': 1}이런 딕셔너리가 생성된다.

같은 종류의 옷은 2벌이상 입지 못하므로, 여러 벌이 있더라도 한 벌만 선택할 수 있다. 예시의 경우 모자는 2C1개 선택이 가능하다. 또, 아예 선택하지 않는 경우인 2C0이 있다. 입고 나갈 모자를 고르는 경우의 수는 2C1+2C0인 것이다.

안경의 경우 한가지 종류만 존재하므로 입거나(1C1) 안입거나(1C0)이 두가지 경우가 존재한다. 안경을 고르는 경우의 수는 1C1+1C0인 것이다.

그렇다면 입고 나갈 옷을 고르는 경우의 수는 총 (2C1+2C0) * (1C1+1C0)개가 된다. 하지만 문제의 조건에서 스파이는 하루에 최소 한 개의 의상은 입습니다.라고 했으므로 옷을 안 입는 경우를 빼줘야한다. 저기서 1만 빼주면 됨.

두번째 입력 예시를 보면 [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] 이와 같은데, 이 경우 {'face': 3}이런 딕셔너리가 생성된다. 역시 얼굴에 착용하는 것도 하나만 고를 수 있으므로 3C1개의 경우의 수가 존재하고, 아예 착용하지 않는 경우의 수인 3C0도 존재한다. 근데 최소 한 개의 의상은 입으니 이 경우도 총 경우의 수에서 1을 빼주면 된다.

이걸 바탕으로 식을 일반화 하는 것이 중요한 포인트인 것 같다.
{'옷 종류 1': n, '옷 종류2': m, '옷 종류3': k, '옷 종류4': p} 라고 했을 때, 서로 다른 옷의 조합의 수는 (nC1+nC0) * (mC1+mC0) * (kC1+kC0) * (pC1+pC0) -1이 된다.
이를 바탕으로 코드를 짜주면 해결!

💻코드

from collections import defaultdict

def solution(clothes):
    clothings = defaultdict(int)
    answer = 1
    for cloth in clothes:
        clothings[cloth[1]] += 1
    for clothing in clothings.values():
        answer *= (clothing+1)
    return answer-1

규칙만 찾으면 코드 짜는 것은 어렵지 않은 문제이다.

📋defaultdict

딕셔너리에서 키값을 지정해주지 않고 호출할 경우 키에러가 뜬다.
하지만 defaultdict를 이용해주면 호출과 동시에 미리 지정한 기본값이 할당되도록 할 수 있다.
defaultdict를 활용해 다음과 같이 기본 값을 int 로 선언해주고,

from collections import defaultdict
d_dict = defaultdict(int)

기존에 없던 키를 호출하면 해당 키가 0으로 자동 초기화된다.

d_dict['new'] # 출력 0

d_dict를 단독 호출하면 defaultdict(<class 'int'>, {'new': 0}) 이와 같이 출력된다. 기본적인 활용은 당연히 딕셔너리니까 똑같이 .values()등을 사용해 줄 수 있다.
기본 값으로 리스트도 넣어줄 수 있고 람다식을 이용해 원하는 초기 값을 지정해주는 것도 가능하다.

📍다른사람 풀이

💻첫번째 코드(Counter, reduce)

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

코드를 하나씩 뜯어보며 사용된 모듈에 대해 설명하고자 한다.

📋Counter

Counter를 사용하면 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체 를 얻게된다. 내가 defaultdict를 사용한 과정을 좀 더 단축할 수 있는..!!

cnt = Counter([kind for name, kind in clothes])

리스트 컴프리헨션을 이용해서 clothes의 1번째 인덱스인 옷종류 kind를 리스트에 담아주고, 거기서 옷 종류의 개수를 Counter로 계산한다.
첫번째 예시로 들면 리스트 안엔 ['headgear', 'eyewear', 'headgear'] 이렇게 담기는 것이다.
Counter를 사용하면 Counter({'headgear': 2, 'eyewear': 1})를 반환한다.

📋reduce

파이썬의 functools 내장 모듈이다. reduce()는 여러 개의 데이터를 대상으로 주로 누적 집계를 내기 위해 사용한다. 내가 반복문을 써서 답을 구한 것을 한줄로 구현할 수 있게 해준다!

reduce(집계 함수, iterable한 객체, 초기 값)

문제에서는 lambda로 집계함수를 나타낸 것이다. 이 코드는 lambda로 집계함수를 나타낸 것이다.
lambda x,y : x*(y+1)은 x 값에 y+1을 곱한다는 뜻으로 내 코드에서 반복문을 돌려가며 answer *= (clothing+1)를 해줬던 것과 같은 기능이다. y는 초기값 1부터 시작하고, 순회 가능한 데이터인 cnt.values()로 y값을 변경시켜 준다. 이렇게 하면 반복문을 사용하지 않고 누적 집계를 낼 수 있다!!
마지막에 옷을 한 벌도 입지 않는 경우를 하나 빼주면 답이 나온다.

💻두번째 코드(해시)

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2
        else:
            clothes_type[t] += 1

    cnt = 1
    for num in clothes_type.values():
        cnt *= num

    return cnt - 1

모듈을 최소화하고 해시를 구현한 코드이다!!

📚해시(Hash)

• 키에 데이터를 저장하는 데이터 구조
• 키를 통해 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라짐
• 보통은 배열로 미리 해시 테이블을 사이즈만큼 생성 후에 사용한다.
• 파이썬의 딕셔너리가 해시테이블의 대표적인 예({key: value})

이 문제에서는 키를 옷의 종류로 두고, 데이터가 옷의 개수인 것이다.
해시를 사용하는 문제를 마주했을 때 키와 데이터를 어떻게 줄 지 결정하는 것이 제일 중요할 것 같다.