프로그래머스

프로그래머스 의상 풀이: 카테고리별 조합의 곱셈 법칙

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

먼저 같은 종류의 의상이 몇 개인지 세고, 각 종류에서 의상을 하나 고르거나 아무것도 고르지 않는 경우를 계산해야 한다. 해시 맵으로 종류별 개수를 세는 것과 곱셈 법칙을 이해해야 하지만, 복잡한 탐색이나 예외 처리는 필요하지 않으므로 Level 2로 판단했다.

1. 문제 요약

의상의 이름과 종류가 담긴 배열 clothes가 주어진다. 매일 최소 한 가지 의상을 입고, 각 종류에서는 최대 하나의 의상만 선택할 수 있을 때 만들 수 있는 옷 조합의 수를 반환한다.

예를 들어 머리 장식이 2개이고 얼굴 장식이 1개라면 각 종류의 선택은 다음과 같다.

  • 머리 장식: 의상 2개 중 하나를 선택하거나 아무것도 선택하지 않음 → 3가지
  • 얼굴 장식: 의상 1개를 선택하거나 아무것도 선택하지 않음 → 2가지
  • 전체 선택: 3 * 2 = 6가지
  • 아무것도 입지 않은 경우 1가지를 제외 → 5가지

중요한 조건은 다음과 같다.

  • clothes의 길이는 1 이상 30 이하다.
  • 의상 이름과 종류는 문자열이다.
  • 같은 종류의 의상은 최대 하나만 입을 수 있다.
  • 최소 한 가지 의상은 반드시 선택해야 한다.
  • 의상의 순서는 결과에 영향을 주지 않는다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

카테고리별 상태와 조합 계산

해시 맵 counts에 의상 종류별 개수를 저장한다. 예를 들어 다음 입력은 종류별로 headgear: 2, eyewear: 1이 된다.

clothes = [
    ["yellow_hat", "headgear"],
    ["blue_sunglasses", "eyewear"],
    ["green_turban", "headgear"]
]

각 종류에 의상이 count개 있으면, 그 종류에서 선택할 수 있는 경우는 count + 1가지다. count개의 의상 중 하나를 입는 경우와 아무것도 입지 않는 경우를 합친 수다.

모든 종류의 선택은 서로 영향을 주지 않으므로 각 종류의 경우의 수를 곱한다. 마지막으로 모든 종류에서 아무것도 선택한 경우는 문제에서 허용하지 않으므로 1을 뺀다.

정답 = (headgear 개수 + 1)
     * (eyewear 개수 + 1)
     * ...
     - 1

종류별 선택 수를 곱하고 공집합을 빼는 이유

의상의 이름 자체는 조합을 세는 동안 중요하지 않고, 각 종류에 의상이 몇 개 있는지만 필요하다. 따라서 의상 이름을 모두 비교하거나 조합을 직접 만들 필요 없이 종류별 개수를 해시 맵에 모을 수 있다.

한 종류에서 최대 하나만 고를 수 있으므로, 같은 종류의 의상 2개를 동시에 입는 경우를 세면 안 된다. count + 1은 정확히 “그 종류의 의상 하나를 고르는 경우”와 “그 종류를 고르지 않는 경우”만 포함한다.

상태 전이와 경계 처리

각 의상을 읽을 때 해당 종류의 개수를 1씩 증가시킨다. 모든 의상을 센 뒤 종류를 하나씩 확인하며 현재까지의 조합 수에 count + 1을 곱한다.

마지막에 1을 빼는 것은 모든 종류에서 선택하지 않은 조합을 제거하는 단계다. 의상이 한 종류뿐이어도 같은 식이 적용된다. 예를 들어 의상 2개가 있으면 2 + 1 - 1 = 2가지로, 두 의상 중 하나를 고르는 경우만 남는다.

오답 접근과 반례

종류별 의상 개수를 단순히 더하면 서로 다른 종류를 조합하는 경우를 놓친다.

head 종류 의상 2개
face 종류 의상 2개

개수의 합은 4이지만, 각 종류에서 고르거나 고르지 않는 경우를 곱하면 (2 + 1) * (2 + 1) - 1 = 8가지다. 예를 들어 head와 face를 함께 선택하는 조합도 있으므로 합이 아니라 곱을 사용해야 한다.

반대로 의상 4개를 각각 입거나 입지 않는다고 계산해 2^4를 사용하면 같은 종류의 의상 두 개를 동시에 입는 잘못된 경우가 포함된다. 선택 단위를 의상 하나가 아니라 의상 종류로 정해야 한다.

시간·공간 복잡도

의상 목록을 한 번 순회해 종류별 개수를 세고, 종류 목록을 한 번 순회해 곱을 계산하므로 시간 복잡도는 O(n)다. n은 의상의 개수다. 종류별 개수를 저장하는 해시 맵의 크기를 k라고 하면 추가 공간 복잡도는 O(k)이며, k <= n이므로 최악의 경우 O(n)다.

3. 문제 해결 코드 (Python)

counts는 의상 종류를 키로, 해당 종류의 의상 개수를 값으로 저장한다. 모든 종류에서 하나를 고르거나 고르지 않는 경우를 곱한 뒤, 아무것도 고르지 않은 경우를 제외한다.

from collections import Counter


def solution(clothes):
    counts = Counter(category for _, category in clothes)
    combinations = 1

    for count in counts.values():
        combinations *= count + 1

    return combinations - 1

Counter는 같은 종류가 등장할 때마다 개수를 자동으로 증가시킨다. combinations를 1로 시작하는 이유는 곱셈을 누적하기 위한 초기값이며, 각 종류의 count + 1을 차례로 곱한다. 문제의 반환값은 정수이므로 마지막 계산 결과를 그대로 반환한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 종류 조합과 공집합 제외를 확인할 수 있다.

assert solution([["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]) == 5
assert solution([["hat1", "head"], ["hat2", "head"]]) == 2

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 한 종류만 있는 경우, 여러 종류의 조합, 같은 종류의 중복 선택 방지를 확인했다.

공식 예제

입력 기대 출력 확인 결과
[["yellow_hat","headgear"],["blue_sunglasses","eyewear"],["green_turban","headgear"]] 5 통과
[["crow_mask","face"],["blue_sunglasses","face"],["smoky_makeup","face"]] 3 통과

추가 검증 1: 의상 종류 하나

입력: clothes = [["hat1", "head"]]
기대 출력: 1
확인 결과: 통과
검증 목적: 한 의상만 있을 때 그 의상을 선택하는 경우만 세는지 확인

추가 검증 2: 같은 종류의 의상 두 개

입력: clothes = [["hat1", "head"], ["hat2", "head"]]
기대 출력: 2
확인 결과: 통과
검증 목적: 같은 종류의 의상을 동시에 선택하지 않고 하나씩만 세는지 확인

추가 검증 3: 두 종류에서 조합하는 경우

입력: clothes = [["a", "head"], ["b", "head"], ["c", "face"], ["d", "face"]]
기대 출력: 8
확인 결과: 통과
검증 목적: 종류별 선택 수를 곱하고 아무것도 선택하지 않은 경우를 제외하는지 확인

5. 다른 풀이 방식 검색 및 비교

각 의상 조합을 직접 만들어 중복을 제거하는 완전탐색도 가능하지만, 종류가 늘어날수록 조합 수가 빠르게 증가한다. 이 글에서는 실제 조합을 만들지 않고 종류별 선택 수만 곱해 경우의 수를 계산한다.

defaultdict(int)로 종류별 개수를 직접 세는 방식도 Counter와 같은 시간 복잡도를 가진다. 이 글에서는 개수 세기라는 의도를 코드에서 바로 드러내기 위해 Counter를 사용했다.

마무리

의상 문제는 의상 하나하나의 조합을 만드는 문제가 아니라, 종류별 선택 경우의 수를 계산하는 문제다. 각 종류에서 의상을 고르거나 고르지 않는 경우를 곱하고, 아무것도 입지 않은 경우를 마지막에 빼면 된다. 해시 맵으로 종류별 개수를 세고 곱셈 법칙을 적용하면 O(n) 시간과 O(k) 공간으로 해결할 수 있다.

관련 문제

  • 베스트 앨범 풀이: 해시 맵으로 장르별 정보를 묶고 정렬 기준에 따라 결과를 선택하는 문제
#해시#프로그래머스#난이도 2