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

문제링크

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

코딩테스트 연습 - 위장 | 프로그래머스

풀이

기본적인 접근은 맞았는데 응용력이 부족했던 문제이다.

조합을 구성할 때 선택하지 않는다는 선지도 같이 포함시켜 계산한다는 것이 포인트이다.

대분류의 조합들을 hash를 통해 count하고 선택하지 않는다는 선지를 포함시켜 각각 +1 해준 뒤

곱하면 되는 것이다.

그리고 스파이가 하루에 최소 한 개의 의상은 입으므로 모두 입지 않는다는 경우의 수를 빼면 답이 된다.

 

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


int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    unordered_map <string ,int> hash;
    
    for(vector<string> pair : clothes ){
        hash[pair[1]]++;
    }

    unordered_map <string ,int>::iterator iter;
    for(iter=hash.begin();iter!=hash.end();iter++){
        answer*=iter->second+1;
    }
    
    return answer-1;
}

예를 들어 

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

상의 / 파란색 티셔츠

인 경우를 생각해보자.

 

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

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

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

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

 

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

각각 경우를 따지자면

 

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

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

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

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

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

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

 

의 경우가 된다.

 

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

 

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

2. 동그란 안경

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

4. 검정선글라스

5. 파란색 티셔츠

 

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