[프로그래머스][C++] 의상

의상

문제 링크

의상

분석

해시를 활용해 조합을 계산하는 문제입니다.

clothes배열에서 의상의 종류가 키, 해당 의상의 종류의 개수가 값이 됩니다.

조합의 계산은 각 카테고리에서 아무것도 선택하지 않은 경우를 포함하므로 다음과 같습니다.
$총 \ 경우의 \ 수 = (A 개수 + 1) * (B 개수 + 1) * … * (N 개수 + 1) - 1$

1을 빼주는 이유는 어떤 의상도 고르지 않는 이유는 옷을 아무것도 입지 않는 경우를 제외해야하기 때문입니다.

입출력 예시의 첫 번째 배열을 보면 headgear에 해당하는 의상 2개, eyewear에 해당하는 의상 1개로 다음과 같은 식이 나옵니다.
$(2 + 1) * (1 + 1) - 1 = 5$

풀이

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    
    unordered_map<string, int> clothesMap;
    
    // 카테고리별 개수 저장
    for(int i = 0; i < clothes.size(); ++i)
    {
        ++clothesMap[clothes[i][1]];
    }
    
    // 나올 수 있는 조합을 계산
    answer = 1;
    for (const auto& pair : clothesMap)
    {
        answer *= (pair.second + 1);
    }
    // 아무것도 착용하지 않는 경우를 제외
    answer -= 1;
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n + m)$입니다.

• clothes를 순회하는 반복문 $O(n)$
• clothesMap을 순회하는 반복문 $O(m)$
• $O(n + m)$

공간 복잡도는 $O(n)$입니다.

• 의상 카테고리별 개수를 저장하는 clothesMap $O(n)$

테스트 1 〉 통과 (0.02ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 4.19MB)
테스트 3 〉 통과 (0.01ms, 4.28MB)
테스트 4 〉 통과 (0.02ms, 4.19MB)
테스트 5 〉 통과 (0.01ms, 3.64MB)
테스트 6 〉 통과 (0.01ms, 4.19MB)
테스트 7 〉 통과 (0.02ms, 4.18MB)
테스트 8 〉 통과 (0.01ms, 3.61MB)
테스트 9 〉 통과 (0.03ms, 3.63MB)
테스트 10 〉 통과 (0.01ms, 4.14MB)
테스트 11 〉 통과 (0.01ms, 3.67MB)
테스트 12 〉 통과 (0.02ms, 3.61MB)
테스트 13 〉 통과 (0.02ms, 4.2MB)
테스트 14 〉 통과 (0.01ms, 3.71MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.01ms, 3.68MB)
테스트 17 〉 통과 (0.01ms, 4.12MB)
테스트 18 〉 통과 (0.02ms, 4.16MB)
테스트 19 〉 통과 (0.01ms, 3.67MB)
테스트 20 〉 통과 (0.01ms, 4.18MB)
테스트 21 〉 통과 (0.01ms, 4.14MB)
테스트 22 〉 통과 (0.01ms, 3.67MB)
테스트 23 〉 통과 (0.01ms, 4.18MB)
테스트 24 〉 통과 (0.01ms, 4.13MB)
테스트 25 〉 통과 (0.01ms, 4.17MB)
테스트 26 〉 통과 (0.02ms, 4.18MB)
테스트 27 〉 통과 (0.01ms, 4.14MB)
테스트 28 〉 통과 (0.01ms, 4.2MB)