[C++] Programmers: 의상

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다.

 

문제의 난이도는 프로그래머스 레벨 3으로, 표기된 난이도와 비교하였을 때 비교적 쉽게 문제를 해결할 수 있었다.

문제 링크

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

문제 분석

 해당 문제는 의상의 종류와 이름이 주어지고, 각 의상의 조합의 수를 찾는 문제이다. 예를 들어 [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]가 clothes Input으로 들어오면 아래와 같은 조합이 가능하다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

따라서 solution 함수에서 값으로 5를 return해야 한다.

문제 풀이

 해당 문제는 수학적으로 접근해야 한다. 의상의 종류 a, b, c... z가 있을 때 답은 (a.count + 1) * (b.count + 1) * (c.count + 1) * ... (z.count + 1) - 1이 된다. 여기서 (a.count + 1)과 같이 count 값에 1을 더해주는 이유는 해당 종류의 옷을 입지 않은 경우의 수 (공집합)를 더한 것이고 해당 수식 마지막에 1을 빼주는 이유는 아무 것도 입지 않은 경우의 수를 빼준 것이다.

 

 따라서 (a.count + 1) * (b.count + 1) * (c.count + 1) * ... (z.count + 1) - 1의 값을 계산하면 문제는 해결된다.

전체 코드

전체 코드는 다음과 같다. 기존에 프로그래머스에서 주어진 헤더 파일에 map과 set을 추가하였다.

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

using namespace std;

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

    map<string, vector<string>> m;
    set<string> clothTypes;

    for (vector<string> cloth : clothes)
    {
        string clothName = cloth[0];
        string clothType = cloth[1];
        m[clothType].push_back(clothName);
        clothTypes.insert(clothType);
    }

    for (string clothType : clothTypes)
    {
        answer *= (m[clothType].size() + 1);
    }
    answer--;

    return answer;
}