프로그래머스/고득점키트/해시/위장

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

알고리즘 연습 - 위장 | 프로그래머스

약간의 경우의 수의 계산에 대한 센스가 필요한 문제다.

우선 알고리즘 설계는, 각 clothes의 벡터내 string vector 원소에 대하여, 두 번째 값인 의상의 종류를 key값으로 갖는 unordered_map 을 만들어서 푼다. 이 때 value는 key값이 나올 때마다 map[key] ++; 로 1씩 증가시켜준다면, 의상의 종류 별로 몇 개를 갖고 있는지(value)를 정리할 수 있다.

여기서 answer = 1로 수정한 뒤, 각 의상 종류별로 (의상 갯수 + 1) 를 곱해준다. (기본적으로 의상 세트를 입는 것은 동시에 일어나는 곱사건이므로 answer에 곱해주는 것이다.) 의상갯수 +1을 하는 이유는 해당 종류의 의상을 장착하지 않은 경우를 의미하며, 이렇게 모든 의상 종류를 순회하며 answer를 갱신한 뒤, 모두 입지 않는 경우 1가지를 빼줘서 구할 수 있다.

[구현 코드]

---

 

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> d;
    for(auto& i: clothes){
        d[i[1]] += 1;
    }
    for(auto& i: d){
        answer *= i.second+1; // 해당 종류의 의상을 입지 않는 경우
    }
    answer -= 1; // 모든 의상을 입지 않은 경우는 포함되지 않으므로 빼주자.
    return answer;
}