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

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

코딩테스트 연습 - 위장

 

풀이

 

수학적인 사고력이 부족해서 잘 접근하지 못했던 문제 같습니다. 

입력받은 복장들을 조합할 때 '복장을 입지 않는다.' 라는 선택지도 포함시켜야 하는 것이 문제 해결의 포인트입니다.

 

첫번째 입력값인 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]] 로 예를 들어보면

 

headgear에 포함되는 복장은 yellow_hat, green_turban, X(입지 않는 경우)

eyewear에 포함되는 복장은 blue_sunglasses, X(입지 않는 경우) 입니다.

이를 통해 조합을 하면 아래와 같이 3x2 = 6개의 조합이 나오는 것을 확인할 수 있습니다.

 

1. yellow_hat, X

2. blue_sunglasses, X

3. green_turban X

4. yellow_hat, blue_sunglasses

5. green_turban, blue_sunglasses

6. X, X

 

이 중에서 마지막의 아무것도 선택하지 않은 경우를 빼주면 이 문제의 정답을 얻어낼 수 있습니다.

 

전체 코드

 

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

int solution(vector<vector<string>> clothes) {
    int res=1;
    unordered_map<string, int> type;
    
    for(vector<string> v : clothes) {
        type[v[1]]++; // v[0] : yellow_hat, v[1] : headgear
    }
    
    unordered_map<string, int>::iterator it;
    for(it=type.begin();it!=type.end();it++) {
        res*=it->second+1; // +1 : 아무것도 선택하지 않는 경우
    }
    return res-1; // -1 : 전부 선택 안한 경우
}