TIL-2024.02.22 - 알고리즘 - 보물지도과 비트 연산

문제 :  https://school.programmers.co.kr/learn/courses/30/lessons/17681

프로그래머스

 

내 1차 코드

const solution = (n, arr1, arr2) => {
    const toStringTwo = (n, arr) => {
        const returnArr = [];
        for (let i = 0; i < arr.length; i++) {
            const tempArrLength = arr[i].toString(2).length;
            const tempString = tempArrLength <= n ? "0".repeat(n - tempArrLength) + arr[i].toString(2) : arr[i].toString(2);
            returnArr.push(tempString);
        }
        return returnArr;
    };

    let newArr1 = toStringTwo(n, arr1);
    let newArr2 = toStringTwo(n, arr2);

    const returnArr = [];
    for (let i = 0; i < newArr1.length; i++) {
        let checkThis = "";
        for (let j = 0; j < newArr1[i].length; j++) {
            const temp = parseInt(newArr1[i][j]) + parseInt(newArr2[i][j]);
            checkThis += temp;
        }
        let convertThis = checkThis.toString().split("");
        let tempString = "";
        for (let i = 0; i < convertThis.length; i++) {
            if (convertThis[i] >= 1) tempString += "#";
            else tempString += " ";
        }
        returnArr.push(tempString);
    }
    return returnArr;
};

 

 

 

답은 맞았지만..

 

이 문제는 비트 연산Bitwise Operation을 묻는 문제입니다. 이미 문제 예시에 2진수로 처리하는 힌트가 포함되어 있고, 둘 중 하나가 1일 경우에 벽 #이 생기기 때문에 OR로 처리하면 간단히 풀 수 있습니다. 아주 쉬운 문제였던 만큼 if else로 풀이한 분들도 많이 발견되었는데요. 정답으로는 간주되지만 이 문제는 비트 연산을 잘 다룰 수 있는지를 묻고자 하는 의도였던 만큼 앞으로 이런 유형의 문제를 풀 때는 비트 연산을 꼭 기억하시기 바랍니다.

이 문제의 정답률은 81.78%입니다. 첫 번째 문제이고 가장 쉬운 문제였던 만큼 많은 분들이 잘 풀어주셨습니다.

 

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

 

 

-------- 비트 연산 & 비트 연산자?

설명:

• 비트 연산: 이진수로 표현된 데이터의 각 비트를 대상으로 하는 연산.
• 비트연산자: , 2진수 단위로 논리 연산을 위해 사용하는 연산자. 
• 비트 단위로 전체 비트를 오른쪽, 왼쪽으로 이동 시킬때에도 사용
• 실행 과정: 2진수 변환 > 비교 (연산) > 10진수(결과 반환)

 

종류:

• AND(&): 두 비트가 모두 1일 때만 결과가 1이 되는 연산입니다. 

const num1 = 5; // 이진수로는 101
const num2 = 3; // 이진수로는 011

const result = num1 & num2; // 비트 AND 연산: 101 & 011 = 001 (이진수)
console.log(result); // 출력 결과: 1

 

 

• OR(|): 두 비트 중 하나 이상이 1이면 결과가 1이 되는 연산입니다.

const num1 = 5; // 이진수로는 101
const num2 = 3; // 이진수로는 011

const result = num1 | num2; // 비트 OR 연산: 101 | 011 = 111 (이진수)
console.log(result); // 출력 결과: 7

 

• XOR(^): 두 비트가 서로 다를 때 결과가 1이 되는 연산입니다.

const num1 = 5; // 이진수로는 101
const num2 = 3; // 이진수로는 011

const result = num1 ^ num2; // 비트 XOR 연산: 101 ^ 011 = 110 (이진수)
console.log(result); // 출력 결과: 6

 

• NOT(~): 비트를 반전시키는 연산으로, 0은 1로, 1은 0으로 변환됩니다.

const num = 5; // 이진수로는 101

const result = ~num; // 비트 NOT 연산: ~101 = 010 (이진수)
console.log(result); // 출력 결과: -6

 

• 왼쪽 시프트(<<): 비트를 왼쪽으로 이동시키는 연산으로, 오른쪽에 0을 추가합니다.

const num = 5; // 이진수로는 101

const result = num << 1; // 왼쪽 시프트 연산: 101 << 1 = 1010 (이진수)
console.log(result); // 출력 결과: 10

 

• 오른쪽 시프트(>>): 비트를 오른쪽으로 이동시키는 연산으로, 왼쪽에 있는 비트를 삭제합니다.

const num = 5; // 이진수로는 101

const result = num >> 1; // 오른쪽 시프트 연산: 101 >> 1 = 10 (이진수)
console.log(result); // 출력 결과: 2

 

 

 

 

참고 영상:

https://www.youtube.com/watch?v=yHBYeguDR0A

 

 

 

 

비트 연산자로 푼 해당 문제. 

function solution(n, arr1, arr2) {
    let result = [];
    for (let i = 0; i < n; i++) {
        let newRow = (arr1[i] | arr2[i]).toString(2);
        while (newRow.length < n) {
            newRow = '0' + newRow;
        }
        newRow = newRow.replace(/1/g, '#').replace(/0/g, ' ');
        result.push(newRow);
    }
    return result;
}