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

https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

1. 실패한 첫 번째 풀이

next_permutation을 통해 직접 조합을 만들어서 answer에 개수를 더했지만 조합을 만드는 과정에서 시간 초과가 났다.

 

#include <bits/stdc++.h>

using namespace std;
int mix_kind(vector<pair<string, int>>kinds, int i);
int solution(vector<vector<string>> clothes) {
    int answer = 0;
    vector<pair<string, int>>kinds;
    kinds.push_back(make_pair(clothes[0][1], 1));
    for (int i = 1; i < clothes.size(); i++) {
        bool isNew = true;
        for (int j = 0; j < kinds.size(); j++) {
            if (kinds[j].first == clothes[i][1]) {//같은종류가 있다면
                kinds[j].second++;
                isNew = false;
            }
        }
        if (isNew) {
            kinds.push_back(make_pair(clothes[i][1], 1));
        }
    }
    // answer = answer+clothes.size();
    for (int i = 1; i <= kinds.size(); i++) {//여러 종류 중 하나 이상 뽑기(조합)
        answer = answer + mix_kind(kinds, i);
    }
    return answer;
}
int mix_kind(vector<pair<string, int>>kinds, int i) {
    int ans = 0;
    //i개 종류를 뽑기
    vector<int>v(kinds.size() - i, 0);
    for (int j = 0; j < i; j++) {
        v.push_back(1);
    }
    do {
        int tmp = 1;
        for (int k = 0; k < v.size(); k++) {
            if (v[k] == 1) {//선택된 종류니까
                tmp = tmp * kinds[k].second;
            }
        }
        ans = ans + tmp;
    } while (next_permutation(v.begin(), v.end()));
    v.clear(); v.resize(0);
    return ans;
}

 

2. 맞은 풀이

 

unordered_map을 통해서 종류를 편리하게 저장하고, 조합에 대해서는 직접 조합해 볼 필요가 없었다.

second에 1을 더하는 이유에 대해서는...!

 

만약 종류가 A,B가 있고 A에는 1,2,3이라는 의상이, B에는 1,2라는 의상이 있다고 하자.

그냥 조합한다고 하면 3*2를 하면 되지만 입지 않는 경우도 있으므로 다시 생각해야 한다.

A의 의상인 1A,2A,3A 세 가지 중에서 하나를 고를 수 있지만 아예 A종류의 의상 자체를 안 입는 경우도 있다.

따라서 셋 중에 하나를 고르는 경우의 수 3과, 아예 고르지 않는 경우 1을 더한다.

모든 종류에 대해서 그 개수에 1을 더한 값을 가지고 서로를 곱하여 조합한다.

하지만, 적어도 하나의, 즉 적어도 한 종류의 의상은 입어야 하므로 모든 종류에 대해 0인 경우 하나를 빼야 한다.

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    unordered_map<string,int>kinds;
    for(int i=0; i<clothes.size();i++){
        kinds[clothes[i][1]]++;
    }
    int tmp=1;
    for(auto i=kinds.begin();i!=kinds.end();i++){
        tmp = tmp * (i->second+1);
    }
    answer = tmp-1;
    return answer;
}