[알고리즘] 프로그래머스_위장

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 단순히 map으로 나눠서 경우의 수를 구하는 문제이다.
• 근데 왜 레벨 2일까?

2. 문제 풀이 과정(삽질)

• 단순히 map으로 가지수 카운트하고 곱해줬다.
• 다시 보니 모두를 꼭 선택할 필요 없이 고르는 경우도 매우 많았다.
• 3개의 종류 A,B,C가 있으면 A, B, C, AB, AC, BC, AB*C 의 가지수를 따져야 한다.
• 이를 위한 수학적 공식이 있나 찾아본다.

3. 문제 해결

• 공식을 따로 찾지 못해서 식을 인수분해 해봤다.
• A + B + C + AB + AC + BC + ABC
  A(1 + C + B(1+C)) + B(1 + C) + C
• (새로운 값 * (1 + 기존값)) + 기존값 의 규칙이 나온다.
• 고수의 코드가 기대되는 문제다.

4. 코드

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    int recurrence = 0;
    map<string, int> hash;
    for(int i = 0; i < clothes.size(); i++)
    {
        if(hash.count(clothes[i][1]))
            hash[clothes[i][1]]++;
        else    
            hash[clothes[i][1]] = 1;
    }
    
    if(hash.size() == 1)
        return clothes.size();
    
    for(auto &i : hash)
        answer = (i.second * (answer + 1)) + answer;
    
    return answer;
}

5. 고수의 코드를 보고 배우기

• 대충 공식은 같은 것 같다
• 점화식으로 계산 했는데, *= 로 간단하게 표현하고, 1부터 시작한것이 차이가 있다.
• 맵도 처음에 없으면 초기화를 하는 코드가 없어도 되나보다.

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    unordered_map <string, int> attributes;
    for(int i = 0; i < clothes.size(); i++)
        attributes[clothes[i][1]]++;
    for(auto it = attributes.begin(); it != attributes.end(); it++)
        answer *= (it->second+1);
    answer--;

    return answer;
}