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

#include <string>
#include <vector>
#include <map>

using namespace std;

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

 

풀이

1. 의상의 종류의 개수을 받는다.
2. 의상의 종류의 개수에서 선택안함을 추가하여 +1씩하고 모두 곱해준다.
3. 모두 선택안함은 없으므로 -1 해준다.

예를 들어 

얼굴 / 동그란 안경, 검정 선글라스 

상의 / 파란색 티셔츠

인 경우를 생각해보자.

 

얼굴을 선택안한다는 선택지 상의를 선택안하다는 선택지를 각각 만들면

얼굴 / 동그란 안경, 검정 선글라스, 얼굴 선택안함

상의 / 파란색 티셔츠, 상의 선택안함

각각 3가지 2가지의 선택지가 생긴다.

 

여기서 그냥 곱해버리면 3X2=6 , 6가지의 경우의 수가 나오는데

각각 경우를 따지자면

 

1. 동그란 안경, 파란색 티셔츠

2. 동그란 안경, 상의 선택안함

3. 검정선글라스, 파란색 티셔츠

4. 검정선글라스, 상의 선택안함

5. 얼굴 선택안함, 파란색 티셔츠

6. 얼굴 선택안함, 상의 선택안함

 

의 경우가 된다.

 

여기서 모두 선택하지 않는 6번의 경우의 수를 제외하면 

 

1. 동그란 안경, 파란색 티셔츠

2. 동그란 안경

3. 검정선글라스, 파란색 티셔츠

4. 검정선글라스

5. 파란색 티셔츠

 

따라서 정답은 5가지가 되는 것이다. 

출처: https://shjz.tistory.com/102 [밤머리 이야기]

[C++, Hash] 프로그래머스 위장 문제 풀이