[프로그래머스 코딩테스트 고득점 Kit - 해시] 위장

해시 문제

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

 

---

[문제 풀이]

 

한 가지 이상의 의상을 사용하여 조합할 수 있는 경우의 수를 구하는 문제입니다.

다른 종류의 옷들을 조합하는 문제입니다. 주의할 점은 하나의 옷을 입고 나면 나머지는 입지 않는 경우가 존재합니다.

 

간단한 경우의 수 문제입니다.

2개의 옷과 3개의 모자가 존재할 때, 가능한 조합의 수가 6개라는 건 자명합니다.

하지만 입지 않는 경우를 넣어 조금 문제를 어렵게 보이도록 하였습니다.

 

 

우선 map을 하나 만들고 주어진 의상 배열을 순회하면서 key로는 의상의 종류를, value로는 가짓수를 기록합니다.

예를 들어 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgearheadgear]]처럼 입력이 들어왔다면

 

• headgear : yellow_hat / green_turban -> 2개
• eyewear: blue_sunglasses -> 1개

이므로 map에는 [[headgear, 2], [eyewear, 1]]처럼 저장합니다.

 

2개의 headgear와 1개의 eyewear가 있으니 2 * 1 = 2 두 가지의 경우가 있습니다.

라고 제출하면 당연히 틀립니다.

 

위에서 주의했듯 한 가지의 옷만 입고 나머지는 입지 않는 경우가 존재하기 때문입니다.

 

이를 해결하기 위해 우리는 의상의 종류마다 옷을 입지 않는 경우를 넣어줄 겁니다.

위의 예시를 다시 빌려서 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]처럼 입력이 들어왔다면

 

• headgear : yellow_hat / green_turban / none -> 3개
• eyewear: blue_sunglasses / none -> 2개

위와 같이 생각합시다.

 

위의 조합으로 나올 수 있는 경우의 수는 3 * 2 = 6개이고 그 종류는 아래와 같습니다.

1. none + none

2. yellow_hat + none

3. blue_sunglasses + none

4. green_turban + none

5. yellow_hat + blue_sunglasses

6. green_turban + blue_sunglasses

 

하지만 문제의 조건에서 의상은 한 가지 이상 입어야 한다고 명시했으므로 1번의 경우인 none + none은 문제의 조건에 위배됩니다.

집합으로 생각한다면 공집합을 제외하기 위해 1을 빼주는 것과 같습니다.

 

즉, map을 순회하면서 (value + 1)을 전부 곱하고 1을 빼준 값이 몇 개의 종류를 입지 않으면서도 한 가지 이상은 입는 경우를 전부 고려한 방법입니다. 

 

---

[소스 코드] / C++

 

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> hashing;
    
    for (vector<string> v : clothes) {
        if (!hashing.insert(make_pair(v[1], 1)).second) {
            hashing[v[1]]++;
        }
    }
    
    int answer = 1;
    for (pair<string, int> p : hashing) {
        answer *= (p.second + 1);
    }
    
    return answer - 1;
}