[Programmers / Hash] - 위장 C++ 풀이

---

 

프로그래머스 - SQL 키트

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

 

 

문제

 

풀이

 

먼저 각 부위에 해당하는 의상의 개수를 구하는 해시맵을 하나 선언한 후,

입력으로 받은 값의 형식이 [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]의 형식이므로 해시맵 myclothes를 선언한 후, myclothes[headgear], myclothes[eyewear]에 각각 몇개의 경우의 수가 있는지를 저장한다.

 

그 후, 조합할 수 있는 옷의 개수를 구하면 되는데 구하는 방식은 아주 간단하다.

반드시 의상을 1개를 입어야하며, 매번 다른 방식으로 입어야 한다는 조건이 있다.

따라서 headgear 2개, eyewear 1개가 있는 보기의 경우에 조합을 구하는 방법은 

yellow_hat을 쓰는 경우, green_turban을 쓰는 경우, 모자를 안쓰는 경우.

blue_sunglasses를 쓰는 경우, 안경을 안쓰는 경우.

이런식으로 고려해볼 수 있는데, 이 때 조합을 구하는 방법은 (2+1) * (1+1) = 6이다.

이 때 모자도 안쓰고 안경도 쓰지 않는것은 제약조건에 의해 불가능하므로 1을 빼준 값인 5가 리턴값이 된다.

 

이를 알고리즘으로 구현하면 아래와 같다.

 

코드

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<vector<string>> clothes) {
    unordered_map <string, int> myclothes;
    int answer = 1;
    for(auto item : clothes)
            myclothes[item[1]]++;
    for(auto tmp : myclothes)
        answer *= (tmp.second+1);
    return answer-1;
}

 

 

평가

 

옷에 대한 모든 조합을 어떻게 구할지 고민에 빠지면 시간을 많이 잡아먹는 문제이다.

경우의 수를 1번 모자를 쓰는경우, 2번모자를 쓰는경우, 그리고 안 쓰는 경우 이런식으로 나눠서 접근해야 단순곱으로 쉽게 문제를 해결할 수 있다.

 

아마 코드길이가 굉장히 길어지게 푸신분들은 모자를 안쓰는 경우, 안경을 안쓰는 경우를 고려하지 않고 그냥 Brute Force방식으로 모든 조합을 구하신 분들일 것 같다.