프로그래머스 - 2개 이하로 다른 비트 (Javascript)

김승민·2023년 1월 5일

js 알고리즘

알고리즘

목록 보기

4/5

문제

[level 2] 2개 이하로 다른 비트 - 77885

문제 링크

성능 요약

메모리: 57.8 MB, 시간: 216.50 ms

구분

코딩테스트 연습 > 월간 코드 챌린지 시즌2

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	`000...0010`
3	`000...0011`	1

f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	`000...0111`
8	`000...1000`	4
9	`000...1001`	3
10	`000...1010`	3
11	`000...1011`	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 1015

입출력 예

numbers	result
`[2,7]`	`[3,11]`

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이과정

오답코드

function solution(numbers) {
    var answer = [];
    for(num of numbers)
    {
        var pivot=[]
        var pivot= num.toString(2).split('').reverse()
        for(var z = 0 ; z< 8-num.toString(2).length ; z++)
        {
            pivot.push('0')
        }
        pivot = pivot.reverse()
        if(pivot[pivot.length-1] == 0) 
        {
            pivot[pivot.length-1]= '1'
            answer.push(parseInt(pivot.join(''),2))
        }
        else
        {
           var copyPivot = pivot.reverse()
           var firstZero = copyPivot.indexOf('0')
           copyPivot[firstZero] = '1'
           copyPivot[firstZero-1] = '0'
           answer.push(parseInt(copyPivot.reverse().join(''),2))
        }   
    }
    return answer;
}

무지성으로 문제를 이해해가며 코드를 작성했더니 시간초과에 걸렸다.
입력값을 2진수로 변환하여 배열로 바꿔준다.
그리고 0을 채워서 모든 입력을 동일하게 8자리의 수로 만들어줘야 한다고 생각했다.
이 부분이 정말 상당히 불필요했던 과정인듯 하다.
아무튼, 이후에 끝이 0으로 끝나는 경우 짝수이기 때문에 0을 1로 바꿔주기만 하면 된다.
그 외에 경우는 홀수인데, 이는 배열을 뒤집어서 0이 처음으로 나오는 곳을 찾은뒤 '01'인 부분을 '10'으로 바꿔주었다. 이게 문제에서 요구한 '비트가 1~2개만 다른 수 중에서 가장 작은 수' 이기 때문이다.
불필요한 부분들을 없애고, 처음부터 다시 코드를 작성했다.

정답코드

function solution(numbers) {
    var answer = [];
    for(num of numbers)
    {
        var pivot=[]
     
        var pivot=  num.toString(2).split('')
        pivot.unshift('0')
        if(pivot[pivot.length-1] == 0) 
        {
            pivot[pivot.length-1]= '1'
            answer.push(parseInt(pivot.join(''),2))
        }
        else
        {
           var copyPivot = pivot.reverse()
           var firstZero = copyPivot.indexOf('0')
           copyPivot[firstZero] = '1'
           copyPivot[firstZero-1] = '0'
           answer.push(parseInt(copyPivot.reverse().join(''),2))
        }
        
    }
    return answer;
}

아까 코드에서는 for문을 통해 0을 모자란 만큼 채워서 8자리의 수로 만들었는데,
그 대신 맨 앞에만 0을 넣어서 문제를 해결한 것이다.
근데, 잘 생각해보면 2진법으로 바꿨을때 끝이 0인 수는 짝수일텐데 굳이 이진수로 바꿔줄 필요가 없다. 그냥 짝수인 경우 1만 더해주면 문제에서 원하는 조건이 해결된다.
그리고 홀수인 경우에도 지금처럼 배열을 reverse()를 통해서 뒤집은 뒤 찾아서 다시 뒤집을 필요도 없었다.. lastIndexOf() 라는 함수가 있기 때문이다.
그래서 정답처리는 됐지만, 구글링과 고민을 통해 답안을 다시 작성해보았다.

function solution(numbers) {
    var answer = [];
    for(num of numbers)
    {
        if(num%2 == 0)
        {
            answer.push(num+1)
            continue
        }
        var bit = '0'+ num.toString(2)
      
        var firstZero = bit.lastIndexOf('0')
        answer.push
        (parseInt
            (
            `${bit.slice(0, firstZero)}10${bit.slice(firstZero + 2)}`, 2
            )
        )
    }
    return answer;
}