https://programmers.co.kr/learn/courses/30/lessons/42578
문제는 따로 설명하지 않고, 링크를 첨부.
전체 경우를 어떻게 조사할 것인지 생각했음.
먼저 한 종류만 입을 경우, .... , K개 입을 경우(k는 옷의 종류 개수)
모든 경우를 각각 구해주고 더 해준다?
각각 구할 때 특정 케이스 개수를 보장하면서, 다양한 케이스가 나와서 너무 복잡했음.
순열, 조합에 대한 설명이 있는 블로그 링크
그래서 생각한 방법이 0이라는 개념으로 0도 한가지 케이스로 보자.
예를 들어 노란 모자, 초록 터번, 선글라스가 있으면
모자 -> 노란 모자, 초록 터번, 0
안경 -> 선글라스, 0
이런식으로 각 집합을 생각 해주면 전체의 경우를 각 옷 종류 케이스마다 개수를 곱해주고 모두가 0이 나올 경우만 -1 해주면 된다.
그럼 문제가 되는 부분은 종류 별 어떻게 모을 것인건가?
cnt를 어떻게 곱할 것인가?
from _collections import defaultdict
def solution(clothes):
# cloth [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]
# [yellow_hat, green_turban] , [blue_sunglasses]
# [] [0] = 2개, [0][] = 1개, [1][1] = 2개 -> 5개
# - - -> (0,1,2) * (0,1) = 6 -> (0,0)안댐 -> 5개
# step 1 종류 별 모아서 수를 세어야 함.
answer = 1
cloth = defaultdict(int)
for name,kind in clothes:
cloth[kind] +=1
for kind, cnt in cloth.items():
answer *= (cnt +1)
# step 2 cnt * cnt * cnt ... -1 = answer
answer -= 1
return answer
from collections import Counter
from functools import reduce
def solution(clothes):
cnt = Counter([kind for name, kind in clothes])
answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
return answer
종류별 cnt를 모으는 방법
- Counter([kind for name, kind in clothes]) 를 통해서 각 종류의 수를 씀.
list에서 cnt를 셀 경우 이용할 수 있는 함수 일듯. // 복잡도는 결국 순회라서 비슷함.
종류별 곱하기- reduce
reduce와 lambda를 통해 한 눈에 보기 좋게 구현함.
배열의 원소 곱 구현 3가지 방법 참고 블로그
리듀스 사용 참고