[프로그래머스 42578] 위장

• 출처: 프로그래머스 42578
• 분류: 해시 · Lv.2

문제

스파이가 가진 의상 목록 clothes가 [이름, 종류] 형태로 주어진다. 매일 다른 조합으로 입되, 최소 하나는 입어야 한다. 서로 다른 조합의 수를 반환하라.

핵심

종류별 개수만 세면 된다. 각 종류마다 “안 입는 경우”를 포함해 (개수 + 1)을 전부 곱한 뒤, 아무것도 안 입는 경우 1을 빼면 답이다.

풀이

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> cnt;

    for (const auto& c : clothes)
        cnt[c[1]]++;

    int answer = 1;
    for (const auto& [type, n] : cnt)
        answer *= (n + 1);

    return answer - 1;
}

메모

• 왜 (개수 + 1)을 곱하는가: 각 종류마다 “그 종류를 안 입는다”는 선택지가 하나 더 있다. 모자 2개면 선택지는 3개(모자A, 모자B, 안 씀).
• 왜 마지막에 -1인가: 모든 종류에서 “안 입는다”를 선택한 경우 = 아무것도 안 입는 경우. 문제 조건에서 최소 하나는 입어야 하므로 제외한다.
• c[1]: clothes의 각 행이 [이름, 종류]이므로 종류는 인덱스 1. 이름은 쓸 일이 없다.
• 이 공식은 경우의 수 곱의 법칙이다. 독립적인 선택(종류별)의 경우의 수를 곱하면 전체 경우의 수가 된다.

복잡도

시간	공간
O(N)	O(N)

N = 의상 개수. 종류 수는 N 이하이므로 곱셈 루프도 O(N).