[프로그래머스] 위장

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

코딩테스트 연습 - 위장

1. 문제 조건 정리

a) 각 카테고리 별로 의상이 있고 입을 수 있는 의상의 모든 경우의 수를 구해야 합니다.

b) 카테고리 당 하나의 의상만 입을 수 있습니다.

c) 같은 이름의 의상은 없습니다.

 

2. 입력 데이터

- N = 30개, 각 요소는 길이 20 이하의 문자열입니다.

 

3. 아이디어

- 카테고리 개수에 따라 nC1 ~ nCn 의 조합을 구한 후

- 선택된 카테고리에 속한 아이템 개수를 곱하면 됩니다.

- 하지만 단순히 조합을 구하는 데에 이어 어떤 카테고리가 선택되었는 지도 확인해야하기 때문에

- 구현도 쉽지 않고 중복된 계산이 많은 것을 알 수 있습니다.

 

- 카테고리에 대한 조합을 구할 필요 없이

- 카테고리의 기본 값으로 '선택하지 않음' 을 추가합니다.

- 이후 가능한 모든 순열을 구한 후

- 모든 카테고리가 '선택하지 않음'을 선택한 경우를 빼주면 됩니다.

 

- count 에서 O(N),  순열을 구하는 데에 O(N) 이므로 O(N) 입니다.

 

4. 구현

- 배열을 순회하며 카테고리가 생성될 때 count = 2를 대입합니다.(기본값 '선택하지 않음'을 포함)

- 이후 dictionary 를 순회하며 순열을 구합니다.

- 끝으로 아무 의상을 선택하지 않은 경우를 빼줍니다.

 

5. 코드

def solution(clothes):
    answer = 0
    spyItems = {}
    for c in clothes :
        if c[1] in spyItems :
            spyItems[c[1]] += 1
        else:
            spyItems[c[1]] = 2
    
    total = 1
    for v in spyItems.values() :
        total *= v
    answer = total - 1
    
    return answer