프로그래머스 위장

문제

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

코드

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

using namespace std;

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

풀이

스파이 옷 조합의 개수를 구하는 문제인데 안입은 경우도 생각을 해야합니다.

예를 들어서

[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]
로 모자 2개, 선글라스 1개가 있다면

1. yellow_hat

2. blue_sunglasses

3. green_turban

4. yellow_hat + blue_sunglasses

5. green_turban + blue_sunglasses

의 다섯개 조합이 나옵니다.

​

처음에 생각한 로직은 해시테이블로 옷의 종류와 각각의 개수를 구하고 재귀함수로 조합을 구하는데 입은 옷의 개수대로 다 구해서 더할려고 했습니다.

예를 들어서 옷의 종류가 3개면 옷을 1개만 입을경우,옷을 2개 입을 경우,옷을 3개 입을 경우를 다 더해주는거죠

예 근데 이렇게 하니까 1번 케이스가 시간 초과가 나더라고요 예 도저히 생각이 안나서 질문하기에 있는 해답을 봐버렸습니다..

​

해답은 안입은 경우를 더해줘서 곱해주면 됩니다. 예를 들어서

[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]
로 모자 2개, 선글라스 1개가 있다면 모자2개에 모자를 안쓰는경우, 선글라스1개에 선글라스를 안쓴 경우를 곱해서 3*2=6개의 조합이 나오는거죠

1. yellow_hat + 선글라스 안낌

2. blue_sunglasses + 선글라스 안낌

3. green_turban +모자 안씀

4. yellow_hat + blue_sunglasses

5. green_turban + blue_sunglasses

6.모자 안씀 + 선글라스 안낌

이렇게 되는거죠 여기서 아무 옷도 안입는 경우는 없으니까 정답에서 -1을 해주면 됩니다.

​