프로그래머스 - 위장

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

접근

처음 접근은 비트마스크를 사용하는 방식 이었습니다.

예를 들어 스파이가 가지고 있는 옷의 종류가 4가지라면

다음과 같은 경우의 수가 나옵니다.

1번째 옷만 입은경우, 2번째 옷만 입은경우, 3번째 옷만 입은경우 ...
1번째와 2번째 옷만, 1번째와 3번째 옷만 ...
...
1234번째 옷 모두 입은 경우

이를 비트마스크로 표현하면

0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
...
1 1 1 1

입니다.

즉 1~(2^N)-1 (N가지 종류의 옷)
까지의 모든 경우의 수를 체크해서, 해당 수가 1이면 해당하는 옷 종류의 개수를 곱해주면 됩니다.

예를 들어 4가지 종류의 옷을 각각 1,2,3,4개 가지고 있다면

0 0 1 1 의 경우에 3*4 = 12개의 경우의 수가 나옵니다.

하지만 이 경우 테스트케이스 1번이 시간초과가 납니다.

익스트림 케이스를 살펴보면, 모두 각기다른 30가지의 옷을 1가지씩 가지고 있다면

가능한 경우의 수는 2^30-1 = 약 10억번의 루프를 돌게되며 각 루프당 해당하는 종류의 옷을 입을 수 있는 경우인지, 아닌지를 판단해야 하기 때문에

시간 복잡도는 O(2^N*N)이 됩니다.

사실 그냥 O(2^N)만 돌려봐도 시간초과가 납니다.

그래서 다른 방법을 찾아봤습니다.

다음은 비트마스크 코드 전문입니다.

#include <string>
#include <vector>
#include <unordered_map>
#include <math.h>

using namespace std;

unordered_map<string, int> clothes_num;
int cpow(int base,int n);
int solution(vector<vector<string>> clothes) {
    int answer = 0;
    int N;
    int t_res = 1;
    for(int i = 0 ; i < clothes.size(); i++){
        clothes_num[clothes[i][1]]++;
    }
    
    N = int(clothes_num.size());
    
    for(int i = 1  ; i <= int(cpow(2, N))-1 ; i++){
        
        int judge = 1;
        t_res = 1;
        for(unordered_map<string, int>::iterator iter = clothes_num.begin(); iter != clothes_num.end(); ++iter){
            
            
            if ((judge & i) != 0) {
                t_res *= iter->second;
            }
            
            judge = judge << 1;
        }
        answer += t_res;
    }
    return answer;
}

접근2

조금만 생각해보면 10억개가 되는 케이스를 모두 고려할 필요없이 경우의 수만 계산해주면 됩니다.

확률과 통계 단원을 배우고 있는 고3수험생 이라면 오히려 쉬웠을 문제 같습니다.

만약 A종류의 옷이 3개가 있다면 경우의 수는 이 3가지를 입는경우 + 이 종류를 입지 않는 경우 1 = 4가지 경우가 됩니다.

이런식으로 모든 종류 옷의 개수에 1을 더해준 후 모두 곱하면 이를 모두 고려한 개수가 나오며

여기서 1을 빼주면 모두 입지않은 경우를 제외하기 때문에 정답이 됩니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <unordered_map>
#include <math.h>

using namespace std;

unordered_map<string, int> clothes_num;

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

후기

역시 뻘짓으로 30분정도 시간이 낭비가 되었긴 했지만, 비트마스크 방식으로 풀어본게 결과와는 상관없이 마냥 나쁘지는 않은 것 같습니다.