[프로그래머스/C++] 위장

프로그래머스: 위장

문제 링크

c++의 map 혹은 그와 유사한 다른 자료구조를 사용해서 쉽게 풀 수 있는 문제이다. 옷을 종류별로 구분해서 저장하기 위해 map<string, vector<string>>으로 선언해 준 후 주어진 배열을 탐색하면서 종류별 배열에 옷을 넣어 주었다. 종류마다 옷을 하나씩 선택(n)하거나 선택하지 않는 경우(1)의 수가 있는데, 서로 다른 옷의 조합의 수를 구하기 위해 종류마다 가능한 경우(총 n+1)를 곱해 준 후 아무것도 선택하지 않는 경우를 빼 준다.

풀이

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    map<string, vector<string>> m; // 옷의 종류, 실제 옷을 저장하는 배열

    for(vector<string> item : clothes) {
        vector<string> tmp;
        tmp = m[item[1]]; // 옷의 종류가 key
        tmp.push_back(item[0]);
        m[item[1]] = tmp;
    }

    for(pair<string, vector<string>> tmp : m) {
        answer *= (tmp.second.size() + 1); // 선택하지 않는 경우를 더해 준다
    }

    answer--;

    return answer;
}