사용자 도구

사이트 도구


ps:problems:programmers:42578

위장

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42578
문제명위장
레벨Level 2
분류

애드혹

시간복잡도O(n*l)
인풋사이즈n<=30, l<=20
사용한 언어Python
해결날짜2021/05/22
태그

고득점 Kit - 해시

풀이

  • 패션왕 신해빈와 동일한 문제. 문제의 원 출처는 Benelux Algorithm Programming Contest 2013이다
  • 의상의 종류가 i가지이고, 각 종류별로 n1,n2,n3,…,ni 개의 의상이 있다고 하면, 가능한 조합의 갯수는 n1*n2*…*ni - 1이 된다.
    • 마이너스 1을 하는 이유는 아무것도 안입는 경우를 제외하기 위해서.
  • 의상들을 한번씩 읽어서 종류별로 분류하는 것이 O(n*l), 조합의 갯수를 계산하는 것은 O(n). 총 시간복잡도는 O(n*l)

코드

"""Solution code for "Programmers 42578. 위장".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42578
- Solution link: http://www.teferi.net/ps/problems/programmers/42578
"""

import collections
import functools
import operator


def solution(clothes):
    counter = collections.Counter(type_ for name, type_ in clothes)
    return functools.reduce(operator.mul, (v + 1 for v in counter.values())) - 1

토론

댓글을 입력하세요:
R​ O U U H
 
ps/problems/programmers/42578.txt · 마지막으로 수정됨: 2021/07/26 17:25 저자 teferi