[알고리즘] 프로그래머스 의상 파이썬

[프로그래머스] LEVEL2 의상

🌱 문제

🌱 나의 풀이

한 종류의 의상 고르는 경우의 수, 두 종류의 의상 고르는 경우의 수, 세 종류의 의상 고르는 경우의 수 등을 모두 더하기 위해 조합을 이용했다.

from itertools import combinations

def solution(clothes):
    answer = 0
    c_dict = {}
    for c in clothes:
        if not c_dict.get(c[1], None):
            c_dict[c[1]] = [c[0]]
        else:
            c_dict.get(c[1]).append(c[0])
            
    for i in range(1, len(c_dict) + 1):
        for tup in combinations(c_dict, i):
            tmp = 1
            for t in tup:
                tmp *= len(c_dict[t])
            answer += tmp
        
    return answer

예상은 했지만 하나의 최종 케이스에서 시간 초과가 발생했다.
삼중 for문이라니... 내가 봐도 별로였던 코드.

고등학교 확률과 통계 문제를 풀 때 정석으로 하나씩 더해가는 방법과 전체에서 일부를 빼주는 방법이 존재하면 후자를 보통 선택한다. 나는 이 문제를 풀 때 그러지 못했다. 무식하게 하나의 알고리즘만 떠올리고 코드로 옮겨간 것이 문제.

코드의 문제라기보다는 내 수학적 알고리즘의 문제였다.

🌱 풀이 재정비

다른 알고리즘을 찾아 코드를 재정비했다.
의상을 고르지 않는 경우를 "None"이라는 옷을 고르는 경우로 취급하는 것.

즉, 아래의 경우 "None"이라는 옷을 하나씩 추가하여

{
	"headgear": ["a", "b", "c"],
    "eyewear": ["d", "e"]
}

{
	"headgear": ["a", "b", "c", "None"],
    "eyewear": ["d", "e", "None"]
}

위와 같이 변환하는 것이다.

이렇게 되면 "None"을 고르는 경우는 headgear 종류의 옷을 고르지 않음을 의미한다.
하지만 headgear와 eyewear 모두 "None"을 고르면 안 되기에(옷을 입지 않는 경우) 마지막으로 1을 빼준다.

def solution(clothes):
    answer = 1
    
    c_dict = {c[1]: [] for c in clothes}
    for c in clothes:
        c_dict[c[1]].append(c[0])
    
    for k in c_dict.keys():
        answer *= len(c_dict[k]) + 1
        
    answer -= 1
    
    return answer

🌱 다른 풀이

len() 함수를 사용하지 않는 풀이

의상의 이름은 불필요한 정보이므로 과감히 제거해도 된다.

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2
        else:
            clothes_type[t] += 1

    cnt = 1
    for num in clothes_type.values():
        cnt *= num
    return cnt - 1

Counter()를 사용하는 방법

리스트 원소의 개수를 세는 Counter() 함수와 누적 연산을 하는 reduce() 함수 사용하기.

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

🌱 얻어가기

from collections import Counter

https://www.daleseo.com/python-collections-counter/

from functools import reduce

https://brownbears.tistory.com/457
https://www.daleseo.com/python-functools-reduce/

그리고 코드를 작성하기 전에 나의 알고리즘에 오류가 없는지, 더 나은 방법이 없는지 꼭 점검하자.