위장 (조합)

하루히즘·2021년 5월 6일

Problem Solving

프로그래머스

목록 보기

6/17

설명

프로그래머스의 위장 문제다.

어떤 스파이가 변장을 위해 옷을 조합해서 입을 때 주어진 옷들로 총 몇 종류의 조합을 만들 수 있는지 계산하는 문제다. 제한은 무조건 최소한 한 가지의 옷을 입어야 한다는 것이다.

예를 들어 모자가 2개(페도라, 야구 모자), 안경이 1개(뿔테 안경) 있을 경우 다음과 같이 총 5가지의 경우가 가능하다.

페도라
야구 모자
뿔테 안경
페도라, 뿔테 안경
야구 모자, 뿔테 안경

헷갈렸던 점은 의상의 종류는 고정된 게 아니고 문제에서 주어지는 종류에 따라 직접 분류해야 한다는 것이다. 예시에서는 얼굴, 상의, 하의, 겉옷 4가지로 예시를 들었지만 실제로는 한 종류부터 30 종류까지 주어질 수 있다.

풀이

조합 (실패)

스파이가 옷장에서 옷을 꺼내 입을 때 상의를 입고 하의를 입든 하의를 입고 상의를 입든 같은 옷이라면 같은 조합의 옷을 입은 것이다. 즉 n개의 후보군에서 k개의 후보를 순서에 상관 없이 선택하는 조합 문제로 보고 파이썬의 itertools 모듈을 사용할 수 있다.

그리고 의상의 이름도 문자열로 주어지지만 어차피 조합의 갯수만 구하는 문제기 때문에 실제로 이를 저장할 필요는 없고 해당 종류의 의상이 몇 개나 있는지만 확인하면 된다.

그렇다면 조합을 어떻게 사용할 수 있을까? 이는 n개의 A와 m개의 B를 조합하는 방법은 n * m이라는 것에서 착안한다.
위의 그림처럼 이 세 종류의 옷을 입는 조합을 계산할 때는 단순히 각 종류의 옷의 갯수를 곱하면 된다.

하지만 문제에서는 최소한 한 가지의 옷을 입도록 제한하고 있을뿐 모든 종류의 옷을 하나씩 입어야 한다는 조건은 없다. 즉 스파이는 모자만 쓰거나 바지만 입을 수도 있다는 것이다.

이 부분에서 조합을 활용하는 방법을 생각할 수 있는데 언급했듯이 하의를 입고 상의를 입든 상의를 입고 하의를 입든 순서는 상관이 없기 때문에 스파이가 입을 수 있는 의상이 n 종류가 있다면 n 종류에서 1 종류, 2 종류, ..., n-1 종류, n종류를 선택하는 조합을 계산하여 총 몇 개인지 계산하면 될 것이다.

즉 nC1, nC2, ..., nCn-1, nCn로 얻은 의상 종류 갯수의 조합을 각각 곱해서 합산하면 된다. 이를 기반으로 구현한 코드는 다음과 같다.

import collections
import itertools


def solution(clothes):
    # 조합의 갯수.
    answer = 0
    # 문제에서 주어진 의상을 저장하는 사전 자료형.
    closet = collections.defaultdict(int)
    # 의상의 종류별로 갯수 파악.
    for cloth in clothes:
        closet[cloth[1]] += 1
    
    # 각 종류별 갯수를 리스트로 변환.
    each_counts = [*closet.values()]
    # n개의 종류 중 1개, 2개, ..., n-1개, n개 선택하는 조합 작성.
    for limit in range(1, len(each_counts)+1):
        candidates = [x for x in itertools.combinations(each_counts, limit)]
        # 각 조합으로 선택된 의상의 가짓수들을 곱셈.
        for candidate in candidates:
            result = 1
            for element in candidate:
                result *= element

            answer += result
    
    # 결과 반환
    return answer

그러나 아쉽게도 대부분의 테스트 케이스를 통과했지만 옷의 종류가 30가지 정도 되는 테스트 케이스에서 시간초과 에러가 발생했는데 아직 해결 방법은 찾지 못했다.

가짓수 계산 (성공)

그래서 풀이를 찾아봤는데 생각보다 훨씬 간단한 방법으로 풀 수 있었다. 바로 해당 종류의 옷을 입지 않는 경우도 하나의 방법으로 생각하는 것이다.
위에서 봤던 그림을 예로 들어보자. 기존에는 옷을 최소한 한 가지는 입는다는 가정 하에 세 종류의 의상을 1개, 2개, 3개씩 조합했지만 해당 종류의 옷을 안 입는 경우도 별도로 마련해두면 굳이 조합으로 해결할 필요가 없다. 왜냐면 상의에서 옷을 안 입는 경우와 하의 4+1 종류, 신발 2+1 종류를 곱하면 상의를 안 입는 조합을 계산할 수 있기 때문이다.

여기에 모든 종류의 의상을 입지 않는(위의 그림에서는 X끼리 조합된 경우) 것은 허용되지 않으므로 전체 가짓수에서 1만 빼주면 모든 의상 조합을 구할 수 있다.

이를 기반으로 작성한 코드는 다음과 같다.

import collections


def solution(clothes):
    # 의상 종류의 가짓수를 보관하기 위한 사전 자료형.
    closet = collections.defaultdict(int)
    # 의상 등록.
    for cloth in clothes:
        closet[cloth[1]] += 1
    
    # 해당 종류의 의상을 입지 않는 경우를 추가하여 리스트로 변환.
    counts = [counter+1 for counter in closet.values()]
    answer = 1
    # 전부 곱셈.
    for count in counts:
        answer *= count
        
    # 모든 종류의 옷을 입지 않는 한 종류를 제외하고 반환.
    return answer - 1