Level 2️⃣ - 2개 이하로 다른 비트

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

 

🚀첫번째 접근 방법

아주 직관적으로 해결하고자 했다.

우선 x를 toString을 이용해 이진법으로 변경한다.

그리고 for문을 돌면서 x보다 큰 수를 이진법으로 변경한 후에 각각의 자리가 맞는지를 일일히 확인한다.

체크 변수를 만들어 자리가 맞으면 체크 변수를 하나씩 늘려준다.

만일 체크 변수의 값이 3이 넘어가면 다음 숫자로 넘어간다.

function solution(numbers) {
    let ret = [];
    numbers.forEach((num)=>{
        let t = num.toString(2);
        for(let i = num+1; ; i++){
            let check = 0;
            let k = i.toString(2);
            if(k.length > t.length) t = '0' + t;
            for(let j = 0; j<k.length; j++){
                if(check > 2) break;
                if(t[j]!==k[j]) check++;
            }
            if(check > 2) continue;
            ret.push(parseInt(k, 2));
            break;
        }
    });
    return ret;
}

 

하지만 시간초과가 나왔다.

왜냐하면 numbers의 길이는 최대 10만이고, number의 요소들은 최대 10^15까지의 수이다.

내 코드로 시간복잡도를 구해보면 number의 요소가 10^15에 가까운 수라면 한번의 연산만으로도 최대 10만 * 10^15의 연산이 발생한다.

코드에 문제점을 발견했으면 다른 방법을 생각해야한다. 이렇게 많은 데이터가 주어진 경우 무식하게 풀 수 없을 때는 문제에 규칙이 숨어있는 경우가 종종있다. 시도해보며 규칙을 발견해야한다.

 

🎯두번째 접근방법

우선 짝수는 이진법으로 변경하면 항상 맨 뒤는 0이다. (이유는 직접 시도해보면 충분히 알 수 있다.)

그렇기 때문에 x보다 크고 비트가 2개 이하로 다른 수들 중 제일 작은 수는 맨 뒤의 0을 1로 바꾼 수이다. 이 말은 짝수에서 1을 더한 수가 문제의 조건에 맞는 수라는 것이다.

홀수는 직접 시도를 해보고 규칙을 찾아보자.

3 ➡ 011

4 ➡ 100

5 ➡ 101

x가 3일 때 조건을 만족하는 f(x)는 5이다.

 

5 ➡ 101

6 ➡ 110

x가 5일 때 조건을 만족하는 f(x)는 6이다.

 

7 ➡ 0111

8 ➡ 1000

9 ➡ 1001

10 ➡ 1010

11 ➡ 1011

x가 7일 때 조건을 만족하는 f(x)는 11이다.

 

규칙을 찾으면 뒤에서부터 '01'을 찾아서 해당 부분을 '10'으로 바꿔주면 된다.

function solution(numbers) {
    let ret = [];
    numbers.forEach((num)=>{
        let k = '0' + num.toString(2);
        if(num % 2 === 0){
            k = [...k].splice(0, k.length - 1).join("") + "1";
            ret.push(parseInt(k, 2));
        }
        else {
            let idx = k.lastIndexOf('01');
            k = k.substring(0, idx) + '10' + k.substring(idx+2);
            ret.push(parseInt(k, 2));
        }
    });
    return ret;
}

lastIndexOf는 indexOf와 다르게 뒤에서부터 역순으로 요소를 찾는다. indexOf는 여러개의 문자가 있는 경우 맨 첫번째의 요소의 인덱스를 반환한다. replace(a, b)도 앞에서부터 a를 탐색하다가 a를 찾으면 b로 변경한다. 하지만 lastIndexOf는 역순으로 탐색해서 찾은 첫번째 요소의 인덱스를 반환한다는 것을 주의하자.

 

그리고 substring은 부분문자열을 반환하는 것이지 기존 문자열을 변경하지 않는다. 주의하자.