[프로그래머스] 위장

코딩테스트 연습 - 위장

풀이

문제를 읽고 의상의 종류에 해당하는 의상의 이름을 해시에 저장해야겠다고 생각했다. 제한사항에 같은 이름을 가진 의상은 존재하지 않는다고 명시되어 있어서 vector에 저장했다.
모든 조합의 가짓수를 구하는 부분에서 조금 생각을 많이 했는데
생각해보니, 스파이는 하루에 최소 한 개의 의상을 입으면 되므로
(각 의상 종류에 해당하는 의상의 개수 + 1)을 다 곱해주고 아무것도 안 입는 경우를 빼주면 쉽게 정답을 구할 수 있다.

ex) 입출력 1번 예시
(yellow_hat, green_turban, 안 입기) X (blue_sunglasses, 안 입기) - 1

+) 굳이 의상의 이름을 저장할 필요 없이 개수만 저장해도 문제를 풀 수 있다!

코드

풀이 1

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map <string, vector<string>> m;
    
    for(auto& i : clothes) m[i[1]].push_back(i[0]);
    
    for(auto& i : m) answer *= (i.second.size() + 1);
    
    return answer - 1;
}

풀이 2

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map <string, int> m;
    
    for(auto& i : clothes) m[i[1]]++;
    
    for(auto& i : m) answer *= (i.second + 1);
    
    return answer - 1;
}