[PS] 의상

문제

프로그래머스

입을 수 있는 의상 조합의 개수 구하기이때 아무것도 입지 않는 경우는 제외해야 한다

 

풀이

처음에는 '각 의상 종류에서 어떤 걸 입을지 일일이 선택해 조합을 구해야 하나?'

싶었지만, 이렇게 하면 경우의 수가 너무 많아지고 코드도 복잡해진다

그래서 더 단순한 방식으로 접근해봤다

 

단순하게 생각해서 의상 종류별로 착용할 수 있는 경우의 수를 구해서 이들을 곱하면 된다

이때, 해당 종류의 의상을 착용하지 않는 경우까지 생각해서 경우의 수를 구해주어야 한다

 

그리고 모든 종류의 의상을 입지 않는 경우의 수는 제외해야 하므로

최종 곱셈에서 나온 결과에서 1을 빼주어야 한다

 

예시

모자 3개, 상의1개가 있는 경우를 생각해보자

모자: [모자 A, 모자 B, 모자 C, 착용 X] / 상의:[상의 A, 착용 X]

모자를 착용할 수 있는 경우의 수는 4가지, 상의를 착용하는 경우의 수는 2가지가 나온다

이때 이 둘을 곱하면 4 * 2 = 8이 된다

모자: [착용X] / 상의: [착용X] 

아무것도 착용하지 않는 경우의 수를 빼면 8 - 1 = 7로 정답이 나온다

 

unordeder_map

그렇다면 의상 종류별 의상의 개수를 어떻게 구할 수 있을까?

이는 각 의상의 종류를 키로, 개수를 값으로 저장하는 unordered_map을 활용하면 쉽게 해결할 수 있다

주어진 의상 목록에서 각 의상을 순회하면서, 해당 의상의 종류를 키로 하여 값을 하나씩 증가시켜주면 된다

 

CODE

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map <string, int> map;
    
    for (auto cloth : clothes)
        map[cloth[1]]++;
    
    for (auto cloth : map)
        answer *= cloth.second + 1;
    
    return answer-1;
}

 

회고

처음에는 문제를 복잡하게 생각해서 unordered_map<string, vector<string>> 형태로 구현하려고 했다

종류별로 어떤 의상이 있는지를 저장하고, 직접 개수를 세는 방식이 떠올랐지만,

어떤 의상을 선택하는 지는 알 필요가 없고, 개수만 카운트 하면 되는 문제였다

 

즉, 각 의상 종류에서 옷을 입거나 입지 않는 경우의 수만 고려하면 되므로,

값은 int로 개수만 저장하면 충분하다는 사실을 깨달았다

이렇게 구현하니까 진짜 세상 편해짐..

 

해시맵 문제는 어렵게 생각하면 구현이 복잡해지기 쉬운데,

문제의 본질을 파악하고 단순화하는 사고 과정이 얼마나 중요한지 느낄 수 있었다.