[프로그래머스 문제풀이] 4. 의상

해시 테이블을 이용하는 unordered_map을 사용하여 의상 종류 별로 개수를 센다.

[1, 옷], [a, 바지], [2, 옷] 이 주어질 때 가능한 조합은

1
a
2
1,a
2,a

이렇게 다섯가지이다.

공식으로 만들면 3+(1*2)가 될 것이다.
이렇게 풀 수도 있겠지만 옷과 바지 뿐 아닌 다른 종류도 있다면 연산이 복잡해진다.

옷 개수를 a,
바지 개수를 b,
신발 개수를 c라고 한다면
공식은

a+b+c+ab+bc+ca+abc

신발만 추가했을 뿐인데 공식이 복잡해졌다.

옷과 바지를 안 입는 것도 포함 시킨다면 무조건 두 개의 조합으로 이루어 져야 한다.
옷을 안 입는 것을 0, 바지를 안 입는 것을 n이라고 한다면 조합은

0,n
1,n
0,a
2,n
1,a
2,a

여섯가지가 나오고 둘 다 안 입은 것은 제외시킨다.
공식으로 만들면 (1+1)*(2+1)-1이다.

여기서 아까와 같이 신발을 추가해 기호로 표시한다면

(a+1)(b+1)(c+1)-1

공식이 훨씬 간단해 졌다.
이제 코드로 적용시켜 보자.

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    unordered_map<string, int> hash_map;

    for (auto data : clothes)
    {
        ++hash_map[data[1]];
    }

    for (auto keyvalue : hash_map)
    {
		answer *= keyvalue.second + 1;
    }

    return answer-1;
}

int main()
{
    cout << solution({{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}}) << '\n';
    cout << solution({{"crow_mask", "face"}, {"blue_sunglasses", "face"}, {"smoky_makeup", "face"}} ) << '\n';
}

실행결과

5
3

의상 문제 링크