[pgs위장]list에 X를 추가하여 combinations 구하기

프로그래머스 위장

itertools.combinations

from itertools import combinations

순열과 조합, 확률 등을 공부할 때 나오는 조합을 구현하는 방법이다. ['headgear', 'eyewear', 'shoes']에서 2개를 뽑는다면, 3C2로 3가지의 경우가 발생할 것이다. combinations(list, 2)로 간단하게 구현할 수 있다.
아래 그림에서처럼 tuple형태로 두 개씩 짝지어진 데이터들이 itertools 형태로 담긴다. list에 담아주어야 계속 사용할 수 있다. 그렇지 않으면 한번 iter가 돌면 사라지기 때문

Question

모든 경우의 수를 세어 보는 문제이다.

Solution

Solution 1

PSEUDO

• count dict를 만든다.
  ex) {'모자': 2가지, '신발': 3가지, '셔츠': 2가지}
• key(의상 종류)를 가지고 combinations를 뽑는다. 모든 가능한 개수를 돌려본다.
  ex) 3가지가 있다면 3C1, 3C2, 3C3
• 모든 콤비네이션에 대해 각 count 개수를 곱해준 값들을 뽑고, 이를 모두 더해서 답을 구한다.
  ex) (모자,신발)이고 모자 2가지 신발 3가지가 있다면 이 콤비네이션은 2*3가지가 나올 수 있다는 뜻

from itertools import combinations as cbs
def sol_1(clothes):
    # make dict
    vocab = dict()
    for name, cat in clothes:
        if cat not in vocab:
            vocab[cat] = 1
        else:
            vocab[cat] += 1
    
    ans = 0
    for num in range(1, len(vocab)+1):
        for com in list(cbs(vocab, num)):
            temp = 1
            for c in com:
                temp *= vocab[c]
            ans += temp
    return ans

Solution 2

접근 방식을 조금 다르게 하면 아주 간단하게 문제가 풀린다. 프로그래밍의 문제라기 보다는 사고력 테스트...

PSEUDO

• 똑같이 count dict를 만들고
• 각각의 count(value)에 +1 해준 후 다 곱해준다.
• 답은 이 값에서 -1 해주면 됨

왜? 아래처럼 생각해보자. 오른쪽처럼 X(입지 않는 경우)를 추가해주면 자연스럽게 hat과 shirt만 입는 경우, shoes만 입는 경우 등을 포함할 수 있다. (A, D, X), (X, X, G) 등으로. 그리고 마지막에 -1을 해주는 것은 모두 X가 선택되는 경우를 제거해줘야 하기 때문이다. 너무나 간단하게 O(n)으로 풀 수 있다.

def sol_2(clothes):
    vocab = dict()
    for name, cat in clothes:
        if cat in vocab:
            vocab[cat] += 1
        else: vocab[cat] = 1
    ans = 1
    for i in vocab.values():
        ans *= (i+1)
    return ans-1

Solution 1은 한 개의 케이스에서 시간초과가 발생, 소요시간만 얼핏봐도 두 코드의 시간 효율 차이가 크다는 것을 알 수 있다. 시간초과가 나면 다르게 접근할 수 있도록 머리를 써야겠다..

github