[프로그래머스] 의상 - python

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

문제 정보

문제 유형	난이도	걸린 시간	해결 유무	스스로 구현 성공
해싱	level2	45m	O	X

설계 방법

1. dictionary에 “옷의 분류 : 종류 갯수” 이렇게 넣어주고

2. (종류+1) 전부 곱한 후 -1 해주면 됨

 

(종류 + 1) 곱하고 1 빼면 되는 이유: ex. (a + 1)(b + 1)(c + 1) - 1 = (a + b + c) + (ab + bc + ca) + abc

코드

def solution(clothes):
    ans = 1
    dict = {}
    for i in clothes:
        if i[1] not in dict:
            dict[i[1]] = 0
        dict[i[1]]+=1

    for i in dict.values():
        ans=(i+1)*ans
    return ans-1

시간 복잡도

O(N)

어려웠던 점

for i in dict.values():
        ans=(i+1)*ans

이 부분은 풀이 보기 전까지도 몰랐음

어떻게 생각해내지

 

(종류 + 1) 곱하고 1 빼면 되는 이유: ex. (a + 1)(b + 1)(c + 1) - 1 = (a + b + c) + (ab + bc + ca) + abc