프로그래머스 42578 - 위장 (Lv.2)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42578

// 프로그래머스 42578 - 위장 (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/42578

// 문제 설명
// 스파이가 가진 의상이 [의상 이름, 의상 종류] 쌍의 배열로 주어진다.
// 매일 다른 조합으로 위장하되, 같은 종류는 최대 1개만 입고 최소 1개는 입는다.
// 가능한 옷 조합의 수를 반환하라.

// 제약 조건
// 1 <= clothes 길이 <= 30
// 같은 이름의 의상은 없다. 이름/종류는 알파벳 소문자와 '_'로만 구성.

// Example
// Input : [["yellow_hat","headgear"],["blue_sunglasses","eyewear"],["green_turban","headgear"]]
// Output: 5   (headgear 2벌 + eyewear 1벌 → 3 x 2 - 1)
//
// Input : [["crow_mask","face"],["blue_sunglasses","face"],["smoky_makeup","face"]]
// Output: 3   (face 3벌 → 4 - 1)

// 접근 — 해시맵 카운팅 + 곱의 법칙
// 조합을 직접 나열하면 부분집합 열거 = 최악 2^30. 수식으로 바꾸면 O(n).
// 1) 종류별 의상 개수 n을 해시맵으로 센다.
// 2) 각 종류의 선택지는 "안 입는다"를 포함해 n + 1가지. 종류 간 선택은 독립이므로
//    전체 경우의 수 = (n1+1)(n2+1)...(nk+1).
// 3) 전부 "안 입는다"를 고른 1가지(알몸)는 규칙 위반이므로 빼고 반환.
// 시간 O(n), 공간 O(종류 수)

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> cnt;                // 의상 종류 → 개수
    for (auto& c : clothes) cnt[c[1]]++;

    int answer = 1;
    for (auto& [kind, n] : cnt) answer *= n + 1;   // 종류마다 "안 입기" 포함 n+1가지
    return answer - 1;                             // 아무것도 안 입는 경우 1가지 제외
}

정리

• 조합을 나열하면 2^30, 수식으로 세면 O(n). “가능한 조합의 개수만 묻고 조합 자체는 안 묻는” 문제는 완전 탐색이 아니라 곱의 법칙 신호다. 카테고리가 ‘해시’인 이유는 탐색이 아니라 종류별 카운팅 도구로 쓰기 때문.
• 핵심은 “안 입는다”를 선택지에 넣는 +1 트릭. 종류마다 (n+1)가지가 되면 종류 간 선택이 독립이라 그대로 곱할 수 있고, “최소 1개는 입는다” 조건은 마지막에 공집합 1가지만 빼면 끝난다. 조건 분기가 수식 안으로 흡수되는 전형적인 케이스.
• 상한 점검: 30벌이 15종류 x 2벌일 때가 최대로 3^15 ≈ 1,434만 — int로 충분. 곱셈 문제는 누적 상한부터 계산하고 자료형을 정한다 (행렬의 곱셈·303과 같은 습관).
• unordered_map<string, int> 카운팅은 이번 주 계속 나온 패턴이다 — 7785 회사에 있는 사람의 map<string,bool> 플래그, 어제 560의 unordered_map<누적합, 횟수>와 같은 계열. 순서가 필요 없으면 unordered_map(평균 O(1)), 정렬 순회가 필요하면 map(O(log n)) 이라는 선택 기준도 재확인.
• 순회에서 auto& [kind, n] 구조적 바인딩(C++17)으로 it->second 없이 바로 개수를 읽었다. 값은 안 바꾸므로 참조로만 받는다.
• 검증: 예제 2개(5, 3)와 경계 케이스(1벌 → 1) 통과 (MSVC /std:c++17 컴파일·실행).