[CodeKata] 프로그래머스: 3.29(월), 후보키 / [이론] 비트 연산자

🥋 Ooooth!! (Level 2)

 

 🧮 풀이

부분집합 등 개념을 활용에서 풀어도 마땅한 방법이 나오지 않았다.

리뷰를 보니 비트 연산자를 활용한 풀이가 많았고, 모범답안을 해석하면서 비트연산자에 대해 간단히 공부했다.

 

🖇 리뷰

- 모범답안

function solution(relation) {
  const cols = relation[0].length;
  const check = 1 << cols;
  const answer = new Set();

  for (let i = 1; i < check; i++){
    let temp = relation.map(x=>x.filter((col,index)=>i & (1<<index)).join(""));
    const set  = new Set(temp);

    if (temp.length === set.size) answer.add(i);
  }

  for (let x of answer) {
    for ( let y of answer) {
      if(x >= y) continue;
      if((x & y) === x) answer.delete(y);
    }
  }

  return answer.size;
}

1) 비트 연산 준비

• cols는 컬럼의 길이(속성 개수)이며, check의 각 자리수는 컬럼의 포함유무를 의미하겠다. 이를 통해, 2^cols 만큼 컬럼조합이 나온다.
• answer는 유일성을 가지는 컬럼조합을 담는 배열이다. 중복을 없애기 위해 Set() 자료형을 활용했다.

2) 유일성 검사

• 반복문을 통해 1부터 15(1111) 까지의 컬럼조합을 탐색한다. 0은 빈 속성들의 집합이므로 제외했다.
• temp는 relation 배열에서 i(컬럼조합) 에 해당하는 속성들로만 filter() 한 뒤, 중복검사를 위해 문자열로 join() 재가공한 배열이다.
• 이 temp와 temp로 만든 Set() 의 길이가 같다면, 중복요소가 없다는 의미로 answer에 해당 i(컬럼조합)을 추가한다.

3) 최소성 검사

• answer 에서 각 컬럼조합을 비교해서 최소성 검사를 진행한다. y가 x보다 큰 경우에 대해서만 진행한다.
• 만약, (x & y)의 중복 컬럼조합이 x(더 작은값)와 같다면 이는 y가 x의 연장 케이스란 의미이다. 그렇기에 answer에서 y를 제거해준다.

 

 

- [이론] 비트 연산자

 

컴퓨터 연산에 최적화된 2진수 연산을 위한 연산자가 바로 "비트 연산자" 인 것이다.

• & : 비교하는 비트가 모두 1이면 1 반환(AND)
• | : 비교하는 비트 중에서 하나라도 1이면 1 반환(OR)
• ^ : 비교하는 비트가 같으면 0, 다르면 1 반환(XOR, 보수법)
• ~ : 다른 연산자와는 다르게 연산을 진행하는 피연산자는 하나뿐이며, ! 연산자와 비슷한 부정연산자로 비트의 값들을 뒤짚는다
• << : 지정한 수만큼 비트 전체를 왼쪽으로 이동(left shift)
• >> : 지정한 수만큼 비트 전체를 오른쪽으로 이동(right shift)
• >>> : 지정한 수만큼 비트를 전부 오른쪽으로 이동, 새로운 비트는 전부 0이 된다

 

& (AND 논리 연산자)

비교하는 비트가 모두 1이면 1 반환

const b1 = 2 & 3;
console.log('2 & 3: ',b1); //2
//2 0010
//3 0011
// 0010 = 2

 

| (OR 논리 연산자)

비교하는 비트 중에서 하나라도 1이면 1 반환

const b2 = 2 | 3;
console.log('2 | 3: ',b2); //3
//2 0010
//3 0011
// 0011 = 3

 

~ (부정 논리연산자)

다른 연산자와는 다르게 연산을 진행하는 피연산자는 하나뿐이며, ! 연산자와 비슷한 부정연산자로 비트의 값들을 뒤짚는다

const b3 = ~4;
console.log('~4: ',b3); //-5
//0000 0100
//1111 1011
//1bit 자리 즉 가장 왼쪽에 있는 것이 부호 비트인데
//1이면 음수, 0이면 양수이다

 

<< (시프트 연산자)

지정한 수만큼 비트 전체를 왼쪽으로 이동(left shift)

const b4 = 4 << 2;
console.log('4 << 2: ',b4); //16
//4를 2비트(2회) 왼쪽으로 이동하라
//0000 0100 4
//0000 1000 8(1회 이동함)
//0001 0000 16(2회 이동함)
//4 * 2 * 2

 

>> (시프트 연산자)

지정한 수만큼 비트 전체를 오른쪽으로 이동(right shift)

const b5 = 4 >> 2;
console.log('4 >> 2: ',b5); //1
//4를 2비트(2회) 오른쪽으로 이동하라
//0000 0100 4
// 000 0010 2(1회 이동함)
// 00 0001 1(2회 이동함)
//4 / 2 / 2

[출처] medium.com/gdana/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EB%B9%84%ED%8A%B8-%EC%97%B0%EC%82%B0%EC%9E%90-5f772ffa35e8