의상(해시, 조합 접근법)

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

프로그래머스

 

문제 내용이나 난이도는 평이하지만

접근 방법을 기억할만하다고 생각해서 포스트를 작성했다.

 

여기서 생각해야하는 점은 모든 종류의 의상을 입지 않아도 되는 것이다.

상의와 바지가 있을때 상의만 입어도(...) 옷을 제대로 입었다고 카운트해준다.

 

옷을 한 종류만 입을 때, 두 종류만 입을 때, 세 종류만 입을 때.... 입을 옷의 종류를 조합하여 계산해나가야 할까?

이렇게 접근한다면 머리가 지끈거리겠지만 아주 쉬운 방법이 있다.

바로 각 종류의 옷에 '입지 않는다'라는 선택지를 넣어주면 된다.

 

• 모자: 흰색 모자, 검정색 모자
• 상의: 빨간색 티, 파란색 티
• 하의: 회색 츄리닝, 국방색 츄리닝

옷의 종류가 다음과 같을 때, 각 카테고리에 '입지 않음'을 넣어준다.

 

• 모자: 입지 않음, 흰색 모자, 검정색 모자
• 상의: 입지 않음, 빨간색 티, 파란색 티
• 하의: 입지 않음, 회색 츄리닝, 국방색 츄리닝

이렇게 된 세 종류의 옷을 조합하게 되면 (입지 않음, 입지 않음, 회색 츄리닝)과 같이 옷을 하나만, 두개만 입었을 때를 포함한 모든 경우의 수가 나오게 된다.

다만, (입지 않음, 입지 않음, 입지 않음)이라는 경우의 수를 고려하여 마지막엔 1을 빼줘야 함에 유의하여야 한다.

 

#include <string>
#include <vector>
#include <map>
using namespace std;

int solution(vector<vector<string>> clothes)
{
    map<string, int> m;
    for (vector<string> cloth : clothes)
    {
        auto iter = m.find(cloth[1]);
        if (iter != m.end())
        {
            (*iter).second += 1;
        }
        else
        {
            m[cloth[1]] = 2;
        }
    }
    int answer = 1;
    for (pair<string, int> elem : m)
    {
        answer *= elem.second;
    }
    answer -= 1;
    return answer;
}