[프로그래머스/C++] 위장

[프로그래머스/C++] 위장

풀었던 문제를 다시 풀어보자!
풀었던 문제가 맞나싶다

1. 문제

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

3. 풀이

• (종류 별 옷의 개수 + 1)를 모두 곱한 후에 1을 빼주면 답이다.
• 1번 종류의 옷을 2벌, 2번 종류의 옷을 3벌 가지고 있다고 가정하면,
  • 1번 종류의 옷을 안 입는다.
  • 1번 종류의 옷 1번을 입는다.
  • 1번 종류의 옷 2번을 입는다
  • 그리고
  • 2번 종류의 옷을 안 입는다.
  • 2번 종류의 옷 1번을 입는다.
  • 2번 종류의 옷 2번을 입는다.
  • 2번 종류의 옷 3번을 입는다.
• 1번 종류의 옷을 입는 경우 3가지와 2번 종류의 옷을 입는 경우 4가지가 나온다.
• 이 둘을 곱하면 1번 종류의 옷과 2번 종류의 옷을 하나도 안 입는 경우부터 둘 중 하나만 입는 경우, 둘 다 하나씩 골라 입는 경우까지 모든 경우가 나온다.
• 옷을 최소한 하나는 입어야 하기 때문에 모두 안 입는 경우 한 가지를 빼주면 답이다.
• 옷의 종류가 늘어나도 똑같다.
• 종류별 옷이 몇 가지가 있는지 알기 위해 map을 사용하였다.
• map을 순회하며 (옷의 개수 + 1)를 answer에 계속 곱해준다.
• 마지막에 1을 빼준다.

4. 처음 코드와 달라진 점

• null

5. 코드

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

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