프로그래머스(Programmers) 위장 - python 풀이

JISU LIM·2023년 1월 11일

Algorithm Study Records

목록 보기

25/79

❓프로그래머스 : 위장

〽️ 문제 요약

스파이가 가지고 있는 서로 다른 종류의 옷의 조합 수를 구하는 문제. 이때 최소 하나의 옷을 입는다.

1️⃣ 시도 1

🤨 접근법 : combinations를 활용해 경우의 수 구하기

입력으로 주어지는 옷의 종류와 이름을 옷의 종류를 키로 하는 해시 테이블에 저장했다. 이 때 중복되는 옷의 이름은 주어지지 않고 경우의 수만 고려하면 되기 때문에 값으로는 옷 종류의 개수를 관리한다.

내가 접근한 방법은 옷의 종류를 1개, …, n개 고르는 경우의 수를 모두 구하는 것이다. itertools 모듈의 combinations를 활용했다. 예를 들어 옷의 종류가 3개 있을 경우 옷의 종류를 1개, 2개, 3개 고르는 경우로 나눌 수 있고 각 종류에서 옷의 수를 a, b, c개라고 할 때,

옷의 종류를 하나 고르는 경우
- a + b + c
옷의 종류를 두 개 고르는 경우
- ab + ac + bc
옷의 종류를 세 개 고르는 경우
- abc

이를 모두 더해 경우의 수를 구했다. 하지만 n=30까지인 테스트 케이스에서 시간 초과가 발생한다.

🔡 코드

from collections import defaultdict
from itertools import combinations

def solution1(clothes):     # 시간초과 (케이스 1)
    answer = 0
    kinds = defaultdict(int)
    for clothe, kind in clothes:
        kinds[kind] += 1
    for i in range(1, len(kinds)+1):
        combs = combinations(kinds, i)
        for comb in combs:
            tmp = 1 
            for kind in comb:
                tmp *= kinds[kind]
            answer += tmp
    return answer

2️⃣시도 2 (참고)

🤨 접근법

경우의 수를 쉽게 구하는 방법이 있다. 바로 각 옷의 종류 별로 안 입는 경우를 고려하는 것이다.

예를 들어 옷의 종류가 위의 예시처럼 3개 있고, 각 종류의 옷의 개수가 a, b, c개라고 할 때, 각 옷의 종류를 안입는 것까지 고려해 모든 경우의 수를 (a+1)(b+1)(c+1)로 구할 수 있다. 단 최소 하나의 옷은 입어야 되므로 모든 종류의 옷을 안입는 경우 하나를 위 경우에서 최종적으로 빼주어야 한다.

결론적으로 옷들의 조합의 수는 (a+1)(b+1)(c+1) - 1이 된다.

+) (a+1)(b+1)(c+1) - 1을 풀어써보면 (abc) + (ab + ac + bc) + (a + b + c)가 된다.

🔡 코드

def solution(clothes):
    answer = 1
    
    kinds = defaultdict(int)
    for clothe, kind in clothes:
        kinds[kind] += 1
    for num_of_kind in kinds.values():
        answer *= (num_of_kind+1)
    
    return answer-1