[위장]

문제 : programmers.co.kr/learn/courses/30/lessons/42578#

코딩테스트 연습 - 위장

 

초기 접근:

• 중복되는 옷이 한 개도 없기 때문에, 경우의 수로 풀면 될 것 같다는 느낌을 받았습니다.
• 초기 접근은 선택하고, 안하고를 반복하여 전체 부분 집합을 만든 다음, answer를 부분 집합의 곱으로 구해주었습니다.
• 해당 접근으로 풀었을 때, 케이스1에서 오답이 발생했고 극단적인 경우를 생각해보았을 때, 2^30 - 1 > 10억이므로 안된다는 것을 알게 되었습니다.

실패 코드(일부):

void PickSum(const int& n, int i, int subSum)
{
    if (i == n) // 0부터 시작
    {       
        answer += subSum;
        return;
    }

    PickSum(n, i + 1, subSum * typeCounter[types[i]]);
    PickSum(n, i + 1, subSum);
}

 

개선된 접근:

• 블로깅을 통해 힌트를 얻었습니다. 경우의 수를 활용한 수학에 가까운 문제임을 알게 되었습니다.
• 입을 수 있는 옷의 종류가 A, B, C 세 가지이고, 각각의 옷의 개수 또한 세 개라고 하면 A의 경우 '안 입는다'까지 포함하여 총 4가지 경우가 있습니다. 옷의 종류마다 이 논리가 적용되므로 위 예에서는 4 * 4 * 4 - 1(모두 안입는다)에 해당합니다.
• 시간복잡도 및 이산적인 수학?에 능해야 겠다고 생각했습니다.

 

코드:

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

using namespace std;

map<string, int> typeCounter;

int solution(vector<vector<string>> clothes) 
{ 
    int answer = 1;
    for (auto& v : clothes)
    {
        typeCounter[v[1]]++;
    }

    for (auto& t : typeCounter)
    {
        answer *= t.second + 1;
    }

    return answer - 1; // 빈 집합 1개 제거
}