프로그래머스 - Level 2. 2개 이하로 다른 비트 / JavaScript (js)

문제설명

문제분석

먼저 문제를 있는 그대로 바라보면, 입력받은 numbers의 각 요소를 순회하면서, 각 요소를 2진법으로 표기했을 때 비트가 1~2개 다른 수를 찾아 그 수로 해당 요소를 업데이트하는 문제입니다.

문제를 해석했으니 코드를 작성해보겠습니다.

이해하기 쉽게 코드작성하기

다음 코드에는 주석이 없습니다. 주석을 굳이 달지 않은 이유는 해당 코드의 다음에 나옵니다. 다음의 코드를 이해하려는 분들을 위해 간단히 설명하면, 각 요소와 요소로부터 1씩 증가한 값을 각각 2진법으로 변환하고 memo에 기록해둡니다. 그리고 이 두 값을 getDiffFromBits 함수로 보냅니다. 이 함수는 비트로 구성된 두 숫자의 길이를 맞춰주고, 뒤에서부터 서로 다른 비트의 수를 카운트합니다. 이때 카운트가 3이되면 항상 3을 리턴합니다. 문제가 비트가 2개 이하로 다른 수 중에서 제일 작은 수를 찾는 것이기 때문입니다.

function solution(numbers) {
    const memo = {};
    return numbers.map(num => {
        memo[num] ??= convertBits(num);
        let diff = 0;
        let i = 0;
        do{
            i += 1;
            memo[num + i] ??= convertBits(num + i);
            const curBits = memo[num];
            const nextBits = memo[num + i];
            diff = getDiffFromBits(curBits, nextBits);
        } while(diff > 2)
        return num + i;
    });
}

function getDiffFromBits(curBits, nextBits) {
    const maxLen = Math.max(curBits.length, nextBits.length);
    [curBits, nextBits] = [setPrefix(curBits, maxLen), setPrefix(nextBits, maxLen)];
    let count = 0;
    for(let i = maxLen - 1; i >= 0; i--) {
        if(curBits[i] === nextBits[i]) continue;
        count += 1;
        if(count > 2) return count + 1;
    }
    return count;
}

function setPrefix(bit, len) {
    return "0".repeat(len - bit.length) + bit;
}

function convertBits(num) {
    return Number(num).toString(2);
}

위 코드는 getDiffFromBits 함수 내에서 for문을 뒤에서부터 실행하여 시간을 1차적으로 줄였고, count가 3이되면 종료하도록 해서 2차적으로 줄였고, memo를 이용해 중복된 숫자를 검사하지 않음에도 다음과 같은 실행 결과가 나타납니다.

어지간하면 제가 시도한 내용에서 전부 통과는 되었어야 하나 시간초과가 발생했습니다. 그렇다는 건 근본적인 접근이 잘못되었다는 걸 뜻합니다. 다시 문제로 돌아가서 조금 고민을 해봅니다.

 

문제는 x보다 크고 x와 비트가 1~2개가 달라야 합니다. 다음처럼 예를 작성해보겠습니다.

• 숫자 | 2진법 | 원하는 숫자 | 원하는 숫자의 2진법
• 2 | 10 | 3 | 11
• 7 | 111 | 11 | 1011
• 11 | 1011 | 13 |  1101

뭔가 윤곽이 나타나는 것 같습니다. 몇 개 더 해보겠습니다.

• 3 | 11 | 5 | 101
• 5 | 101 | 6 | 110
• 6 | 110 | 7 | 111
• 13 | 1101 | 14 | 1110

해당 문자열을 조회하면서 가장 뒤에있는 0을 1로 변환하고, 그 다음 자리가 존재한다면 0으로 변환합니다. 다시 살펴보겠습니다.

• 2 => 3 | 10 => 11
• 3 => 5 | 011 => 101
• 5 => 6 | 101 => 110
• 6 => 7 | 110 => 111
• 7 => 11 | 0111 => 1011
• 11 => 13 | 1011 => 1101
• 13 => 14 | 1101 => 1110

이 결과를 만들어내는 코드를 작성하면 다음과 같습니다.

function solution(numbers) {
	// map으로 각 요소에 접근
    return numbers.map(el => {
    	// 요소를 2진법으로 변환
        let base2ForEl = Number(el).toString(2);
        2진수에서 가장 뒤에 있는 "0"의 index를 확인
        let idx = base2ForEl.lastIndexOf("0");
        // index가 가장 뒤에 있다면 
        if(idx === base2ForEl.length - 1) {
        	// 가장 뒤의 글자만 "1"로 업데이트
            base2ForEl = base2ForEl.slice(0, idx) + "1";
        } else {
        	2진수에 "0"이 없는 경우 맨 앞에 "0"을 추가하고 index를 0으로 업데이트
            if(idx === -1) {
                base2ForEl = "0" + base2ForEl;
                idx = 0;
            }
            // 0의 위치를 기준으로 앞부분 + "10" + 뒷부분
            base2ForEl = base2ForEl.slice(0, idx) + "10" + base2ForEl.slice(idx + 2);
        }
        // 10진수로 변환
        return parseInt(base2ForEl, 2);
    });
}

2진수니까 짝수로 변환해서 비교하는 방법도 있을 거 같긴 한데, 오늘은 시간이 너무 늦은 관계로 이쯤하도록 하겠습니다.