[PRO] 위장

천호영·2022년 4월 28일
0

알고리즘

목록 보기
11/100
post-thumbnail

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)

공식이 존재한다는 사실을 안 뒤에 제출한 풀이는 다음과 같다.
공식은 a+b+c+ab+ac+bc+abc=(a+1)(b+1)(c+1)1a+b+c+a*b+a*c+b*c+a*b*c = (a+1)(b+1)(c+1) -1 이다.

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

정리

  • functools.reduce(function, iterable[, initializer])

    누적하며 함수를 적용하게 한다. initializer가 있으면 sequence 앞에 위치하여 먼저 계산되고, 빈 sequence일 때의 default값 역할도 할 수 있다.(공식문서)

reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) # calculates ((((1+2)+3)+4)+5)
  • collections.Counter([iterable-or-mapping])

    Counter는 해시 가능한 객체를 세기 위한 dict 서브 클래스이다. 따라서 dict에서 사용하던 메소드들이 적용된다. (공식문서)

    특히, 유용하게 쓰이는건 .most_common([n])으로 n 개의 가장 흔한 요소와 그 개수를 가장 흔한 것부터 가장 적은 것 순으로 나열한 리스트를 반환한다. n이 생략되거나 None이면, 모든 요소를 반환하고, 개수가 같은 요소는 처음 발견된 순서를 유지한다.

Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]

profile
성장!

0개의 댓글