[프로그래머스] 해시 - 위장

프로그래머스 - 위장

문제 설명

스파이가 가진 서로 다른 옷의 조합의 수 return하기

제한사항

스파이가 가진 의상의 수는 1개 이상 30개 이하이다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이다.
모든 문자열은 알파벳 소문자 또는 _ 로만 이루어져 있다.
스파이는 하루에 최소 한 개의 의상은 입는다.

문제풀이

옷의 종류를 나눠서 map을 만든다. (모자, 상의, 하의끼리 나눈다.)
map에서 key는 옷의 종류이고 value는 종류의 개수이다.

각 종류의 개수 + 1 한 값을 모두 곱한다.
1을 더하는 이유는 해당 종류의 옷을 선택하지 않는 경우를 포함하기 위해서!
결과에 1을 빼주면서 아무 옷도 입지 않는 경우를 제외시킨다.

코드

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map <string, int> Clothes;
    vector<string> clothesKinds;
    
    for(int i=0; i<clothes.size(); i++){
        if(Clothes[clothes[i][1]] == 0){
            Clothes[clothes[i][1]] = 1;
            clothesKinds.push_back(clothes[i][1]);
        }
        else{
            Clothes[clothes[i][1]]++;
        }
    }
    
    map <string, int>::iterator iter; 
    for(iter=Clothes.begin(); iter!=Clothes.end(); iter++){
        answer*=iter->second+1;
    }

    return answer-1;
}

시간 복잡도

Θ(N)

문제 풀 때 참고 사이트

map container 정리 및 사용법
vector container 정리 및 사용법