비트마스킹 : 카카오 2019 - 후보키

주의할점.

  • 0부터 시작하면 안된다. 최소 1부터 시작해야 한다.
    0000 은 포함되지 않는 것이므로 set에 저장되는 것을 막자.

  • 비트마스킹은 반드시 괄호를 하자.

  • 상수로 표현해서 나머지 테스트케이스에서 통과가 되지 않았다

1. 제한사항을 보고 동일한 조건에서 실행되지 않는다는 것을 파악후에 문제를 접근해야 한다.

2.문제를 직접 풀어보니 어느 for문을 최상위로 올려야 할지 고민했다.


-> relation을 최상위에 올리기에는 올리면 학번 6개의 유일성 포함을 못시키고 반복문이 종료되므로, 비트연산 for문을 최상위로 올려서 6명의 사람을 모두 체크하면서 가지고 있는 속성을 모두 검사하는 방식으로 진행했다.

어려웠던점...

: 최소성???
유일성이 만족한 키를 하나라도 제외 가능하면 유일성이 깨진다고 하는데
순차적으로 비트 연산자가 0001 ~ 1111 진행 중에
먼저 완료된 값이 다음값에 포함되어 있을 때를 의미한다.
뭔소리냐면
(이름 - 전공) 은 유일성과 최소성에 일치한다.

이름과 전공으로 구성된 나열된 값은 중복되는 값이 없으므로 유일성에 적합하고, 이름과 전공 2개의 속성 에서는 유일성에 포함된 속성이 없으므로 최소성에도 적합하다.
윗단에서 유일성과 최소성에 적합한 친구는 학번 하나이다.

그다음 진행하다 보면 예시에서 (학번 - 이름 - 전공) 인데
어떠한 이유에서는 모르겠지만, 최소성에 어긋난다고 한다.
왜 그런지에 대한 이유를 찾아내는 것이 관건이다!
왜냐하면 최소성에 의미를 분석해보면,, 이미 유일성을 만족하는 속성 중 하나라도 제외한다고 하는데, 이뜻은 속성 중에서 유일성이 내포된 속성들을 가지고 있따면 최소성에 어긋난다는 것을 의미한다.
(학번 - 이름 - 전공) 에서 이미 윗단에서 (이름 - 전공)이 유일성에 포함되어 잇으므로 (학번 - 이름 - 전공)은 카운팅 안한다고 유추할 수 있고,
그렇다면 코드로 구현한다면
(학번 - 이름 - 전공) : 1110 vs (이름 - 전공) 0110 이다.
가운데 이름 전공이 11이므로 카운팅안한다라고 유추할수 있으며
이거를 어떻게 표현할지가 관건이다!

풀이전략

: 문제를 보고 어떻게 비트 연산자를 생각해낼수 있는지가 관건이다.

  • 특성이 8이하이기 때문에 비트연산자를 사용하자.??

  • 문제를 보고 정확히 파악하자.
    1) 학번은 중복되는 것이 없으므로 유일성에 맞다. -> 최소성 적합.
    2) 이름은 중복되는 것이 있으므로 apeach 유일성에 어긋난다.
    3) 이름과 전공은 유일성에 맞다. 왜냐하면 이름과 전공을 보며 중복되는 것이 없기 때문이다. 최소성을 보면,
    최소성이란 유일성을 가진 키 라고 했는데, 이름과 전공은 유일성을 가지고 있지 않으므로 <이름,전공>은 적합하다.
    이름만으로는 식별되지 않고, 전공만으로는 식별되지 않기 때문에 최소성에 적합하다.

4) 이름과 전공, 학년인데 중복되는 것이 없으므로 유일성에 적합하다.
4번에서 좀 이해하기 어려웠는데,,,
이름 - 전공 - 학년
-> (이름 - 전공)이 먼저 진행되면서 유일성을 가지게 된다.
이름- 전공을 제외하면 학년인데, 학년은 유일서에 어긋나므로
=> 이름 - 전공 - 학년은 적합하지 않다.

비트로 표현하면

1(0001) - 학번
2(0010) - 이름
3(0011) - 이름, 학번
4(0100) - 전공
5(0101) - 학번, 전공
6(0110) - 이름, 전공
7(0111) - 학번, 이름, 전공
8(1000) - 학년
9(1001) - 학번, 학년
10(1010) - 이름, 학년
11(1011) - 학번, 이름, 학년
12(1100) - 이름, 학번
13(1101) - 학번, 전공, 학년
14(1110) - 이름, 전공, 학년
15(1111) - 학번, 이름, 전공, 학년

유일성 체크

//문제에서 학번은 유일하므로 포함이 된다고 했다.
-> 100,200,300,400,500,600 인데 중복체크를 하는 stl은 set이 있으므로

  • set을 이용해 유일성을 확인하면 된다.
    어떻게 확인할 것이냐? set에다가 다 집어넣은 다음에 size와 set의 size를 비교하면 된다.
    //이름, 전공, 학번은 중복되므로 cnt수에 포함 안시킨다.

최소성 체크

: 어떻게 접근할 것인가가 관건인다.
크게 2가지 방법이 있다.
1) 예를 들어 학번 + 전공을 set에 넣어 유일성 체크 후에, 비교하는 방식이 있꼬,
2) 비트 연산자를 그대로 이용하는 방법이 있다.

  • 예시

    유일성이 완료된 것 중에서 , 비트 중 1이 최소성이라고 생각하면
    0001(학번) 과 0011(학번 - 이름은) 학번쪽 1이 겹치므로 최소성에 어긋 나는 것을 생각할 수 있다.

0001(학번) 과 0110(이름 - 전공) : &했을때 1이 나오지 않으므로 문제 없다.

0001(학번)과 1110(학년 - 이름 - 전공)은 &했을때 1이 나오지 않지만,
1110의 최소성, 유익성을 가진 키 (이름 - 전공)을 제외하면 학년인데,,,
안된다.
비트와 연관지어서 생각하면
(이름 - 전공) 0110 vs (학년 - 이름 - 전공) 1110
이름 전공이 유일성에 포함되어 있으므로 카운팅에 포함하지 않는다.

=>
문제를 보고 최소성에 곶혀서 속성 키값을 빼는 방식으로 접근할 수 있찌만,
규칙성을 발견해서 접근하면 쉽게 접근할 수 있따.

코드로...

  • 어려웠던 점은 100ryan을 표현하기 위해서는
    0001 0010
    100 ryan
    200 apeach
    300 tube
    400 con
    500 muzi
    600 apeach

0001 에서 -> 0010으로 먼저 접근해야 한다는 점이다.
100 -> ryan
따라서 비트 비교를 하면서 string 값에다가 누적해야 한다.

중요한 점.


-> & 연산자 우선순위가 == 보다 낮아서 반드시 ()괄호를 통해 묶어줘야 한다.
안묶으면 답 도출 못한다.

소스코드

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

//학번은 1인데 포함, 11이 들어왔을때 확인해야 한다.
bool compare(vector<int>v, int bit)
{
    for(int i = 0; i< v.size(); i++)
    {
        if((bit & v[i]) == v[i])
            return false;
    }
    
    return true;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    
    vector<int>v;
    
    int row = relation.size(); // 6개
    int col = relation[0].size(); //4개
    
    for(int i = 1; i< (1 << col); i++)
    {       
        set<string>s;
        for(int j = 0; j < row; j++)
        {
            string word ="";
            
        //만약에 이름 전공일 경우에는 유일성을 완료하기 위해서 
            for(int k = 0; k < col; k++)
            {
                if(i & (1 << k))
                {
                    word += relation[j][k];
                }
            }
            s.insert(word);
            
        }
        
        if(s.size() == row && compare(v, i))
        {
            v.push_back(i);
        }
        
    }
    
    answer = v.size();
 
    return answer;
}

//학번은 유일성에 포함된다.
    //이름 전공도 유일성에 포함된다.
    //이름 전공 학년은 유일성에 포함되지만, 이름 전공이 먼저 유일성에 포함되므로 최소성에서 벗어난다.
    
    //모든 경우의 수를 나열할 경우. 
                    //학년 전공 이름 학번 
    //    1     0001    학번 
    //    2     0010    이름
    //    3     0011    이름 학번 
    //    4     0100    전공
    //    5     0101    이름 학번  
    //    6     0110    전공 학번  
    //    7     0111    학년 학번 
    //    8     1000    학년
    //    9     1001    학년 학번
    //    10    1010    학년 이름
    //    11    1011    학년 이름 학번 
    //    12    1100    학년 전공 
    //    13    1101    학년 전공 학번
    //    14    1110    학년 전공 이름
    //    15    1111    학년 전공 이름 학번  
    //=> 선택하고 안하고 이므로 비트마스킹으로 모든 것을 확인해야 한다. 

좋은 웹페이지 즐겨찾기