[프로그래머스] [C++] 위장 (map)

1. 문제

[의상 이름, 의상 종류] 로 이루어진 배열이 주어진다.

 

이때 입을 수 있는 모든 경우의 수를 구하여라

 

단, 의상은 하나이상 입어야한다, 모든 종류를 다 입지 않아도 된다.

 

 

 

 

2. unordered_map

이 문제는 의상의 종류를 해쉬맵에 넣으면 간단하게 해결할 수 있다.

 

의상의 종류를 키로, 값을 한 종류의 의상들의 개수로 설정하면

 

다음과 같은 점화식을 유도할 수 있다.

 

answer = Π(map[key[i]] + 1) -1

 

여기서 +1 은 입지않은 경우를 나타내고 -1은 전부 입지 않은 경우를 나타낸다.

 

 

#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> clothesMap;
    vector<string> keySet;
    
    for(auto& vs: clothes)
    {
        if(clothesMap.count(vs[1]) == 0)
        {
            clothesMap[vs[1]] = 1;
            keySet.push_back(vs[1]);
        }
        else 
            clothesMap[vs[1]]++;
    }
    for(int i = 0; i < keySet.size(); i++)
        answer *= (clothesMap[keySet[i]]+1);
    
    return answer - 1;
}

 

 

 

 

3. 반성

map의 사용에 있어서 미숙하였다.

 

위의 코드인 경우 keySet을 따로 두지 않아도 

 

iterator로 모든 원소를 탐색할 수 있었다.

begin    end

    for(auto it = um.begin(); it != um.end(); it++)
        answer *= (it->second+1);

또한 원소를 삽입할때에도 해당 원소가 있는지 없는지 판단하지 않아도 다음과 같은 코드가 작동한다.

    for(int i = 0; i < clothes.size(); i++)
        um[clothes[i][1]]++;

#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> clothesMap;
    
    for(auto& vs: clothes)
        clothesMap[vs[1]]++;
    for(auto it = clothesMap.begin(); it != clothesMap.end(); it++)
        answer *= (it->second +1);
    
    return answer - 1;
}

 

 

 

코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr)