프로그래머스 42578 의상 (C++)

문제 링크

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

문제 요약

코니가 입을 수 있는 의상의 경우의 수를 구하는 문제입니다.

풀이

입을 수 있는 의상의 모든 경우의 수를 구하려면 각 의상 종류별 갯수를 곱하면 됩니다.

예) 얼굴 의상 수 * 상의 의상 수 * 하의 의상 수 = 입을 수 있는 모든 경우의 수

 

그러나 특정 의상을 입지 않는 경우도 가능하므로, 입지 않는 경우를 위해 1을 더하여 곱해줍니다.

예) (얼굴 의상 수 + 1) + (상의 의상 수 + 1)* (하의 의상 수 + 1) = 특정 의상을 입지 않는 경우가 반영된 경우의 수

 

문제의 조건에서 아무것도 입지 않는 경우는 허용하지 않으므로, 위에서 계산한 경우의 수에서 얼굴 안입음 + 상의 안입음 + 하의 안입음 경우의 수 1을 빼주면, 문제의 답을 구할 수 있습니다.

 

의상 종류별 갯수를 구하기 위해 map을 사용해도 괜찮지만, unordered_map을 사용하면 원소 삽입 시 일어나는 정렬 비용을 아낄 수 있습니다. (현재는 원소들의 정렬이 필요한 것이 아니므로.. map은 내부적으로 레드블랙트리로 구현되어 있기에, 매 요소 삽입마다 정렬을 합니다)

코드

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> count;
    
    for (const auto& c : clothes)
        count[c[1]]++;
    
    int answer = 1;
    for (const auto& [category, n] : count)
        answer *= (n + 1);
    
    return answer - 1;
}