python 코딩테스트 - 의상

출처 : 프로그래머스

처음 든 생각

- 카테고리만 확인해서 조합을 짜봐야겠다

- 조합이니깐 combination 라이브러리를 활용해서 모든 조합 구한 다음에 만약 같은 카테고리의 아이템이 있으면 배제하고 카운트를 해야겠다.

 

나의 답

from itertools import combinations
def solution(clothes):
    answer = 0
    l = []
    x = []
    for i in clothes:
        l.append(i[1])
    for i in range(len(l)):
        x.append(list(combinations(l,i+1)))
    for j in x:
        for k in j:
            if len(set(list(k))) == len(list(k)):
                answer+=1
    return answer

카테고리만 담을 리스트를 만들어주고 카테고리 리스트를 토대로 combination을 수행한다. combination을 통해 조합의 개수별로 리스트를 별개로 만들어주었기 때문에 반복문을 한 번 더 돌면서 겹치는 게 있는지 없는지 확인하였다. 이 과정은 set을 통해 알고리즘을 구상했다. 

 

결과는 맞았지만 시간 복잡도가 O(n^2)이기 때문에 시간초과로 문제를 틀렸다. 이중 반복문 대신 한 번의 반복문을 사용해서 풀 수 있을지 방법을 찾는데 어려움을 겪었다.

 

이 과정에서 수학적인 접근을 도입하였다. 

 

def solution(clothes):
    answer = 1
    l = {}
    for i in clothes:
        if i[1] in l:
            l[i[1]] += 1
        else:
            l[i[1]] = 1
    tmp = list(l.values())
    for i in tmp:
        answer *= (1+i)
    return answer - 1

다항함수의 전개로 접근하여 계수의 합이라고 하게 되면 총 조합의 가짓수가 나오게 된다. 최고차항의 계수 1만 빼주면 되므로 훨씬 더 짧은 시간으로 문제를 해결할 수 있다.

 

사실 이 수학적 접근은 스스로 생각하기 어렵다고 생각한다. 다항식의 전개로 문제를 풀 수 있다는 것도 항상 염두에 두고 고민을 해봐야할 것 같다.