https://programmers.co.kr/learn/courses/30/lessons/42578
초반에 해시를 통해 입력을 받아야 하는 부분을 제외하고는 공식을 찾아내는 수학 문제에 가까웠다.
공식의 존재를 알지 못했을 때 제출했던 풀이는 다음과 같다. 정직하게 모든 경우를 더했고, 시간초과가 났다.
from collections import defaultdict
from itertools import combinations
from functools import reduce
def solution(clothes):
answer = 0
# 입력받아서 종류의 수를 list에 저장
input_dict = defaultdict(int)
for one_cloth_pair in clothes:
input_dict[one_cloth_pair[1]] += 1
cloth_kind_nums = list(input_dict.values())
answer += sum(cloth_kind_nums) # 1개의 cloth만 입을 때 경우의 수 더하기
for wear_cloth_num in range(2, len(cloth_kind_nums) + 1):
wear_cloth_idxs = combinations(range(len(cloth_kind_nums)), wear_cloth_num)
for wear_cloth_idx_tuple in wear_cloth_idxs:
answer += mutiple_on_idxs(cloth_kind_nums, wear_cloth_idx_tuple)
return answer
def mutiple_on_idxs(cloth_kind_nums, wear_cloth_idx_tuple):
filtered_cloth_kind_nums = [x for i, x in enumerate(cloth_kind_nums) if i in wear_cloth_idx_tuple]
return reduce(lambda x, y: x * y, filtered_cloth_kind_nums)
공식이 존재한다는 사실을 안 뒤에 제출한 풀이는 다음과 같다.
공식은 이다.
def solution(clothes):
# 입력받아서 종류의 수를 list에 저장
input_dict = defaultdict(int)
for one_cloth_pair in clothes:
input_dict[one_cloth_pair[1]] += 1
cloth_kind_nums = list(input_dict.values())
one_plus_cloth_kind_nums = list(map(lambda x: x+1, cloth_kind_nums))
return reduce(lambda x, y: x*y, one_plus_cloth_kind_nums) - 1
여기서 다른 풀이를 참고하여 개선이 가능한 부분은 Counter객체를 이용하는거다.
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
누적하며 함수를 적용하게 한다. initializer가 있으면 sequence 앞에 위치하여 먼저 계산되고, 빈 sequence일 때의 default값 역할도 할 수 있다.(공식문서)
reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) # calculates ((((1+2)+3)+4)+5)
Counter는 해시 가능한 객체를 세기 위한 dict 서브 클래스이다. 따라서 dict에서 사용하던 메소드들이 적용된다. (공식문서)
특히, 유용하게 쓰이는건 .most_common([n])으로 n 개의 가장 흔한 요소와 그 개수를 가장 흔한 것부터 가장 적은 것 순으로 나열한 리스트를 반환한다. n이 생략되거나 None이면, 모든 요소를 반환하고, 개수가 같은 요소는 처음 발견된 순서를 유지한다.
Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]