[프로그래머스] 77885 - 2개 이하로 다른 비트

알고리즘은 조금씩 풀고 있었는데, 문제를 풀고 복기할 겸 오랜만에 업로드해본다 😇
푼 문제도 복습할 겸 업로드할 계획

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

프로그래머스

 

문제 파악

• 비트 연산을 잘 활용하여 풀어야겠다
• 비트가 1~2개 다르다는 점을 활용할 수 있을 것 같다.

문제

 

제한사항 & 입출력

 

어려운 점

• 생각보다 케이스가 많다 [0, 100,000]
• 자료형이 long 타입 - [0, 10^15]이기 때문에 비트 연산자라도 연산 횟수가 큰 편

아래와 같은 코드 작성 시 타임아웃이 발생해서 헤맸다

public long[] solution(long[] numbers) {
    for (long n : numbers) {
        long another = n + 1;
        while (true) {
            if (differenceCount(n, another) <= 2) {
                answer[answerIndex++] = another;
                break;
            }
            another++;
        }
    }
    return answer;
}

 

기준 숫자로부터 1씩 더해 해당 비트와 기준 비트의 차이를 검사하는 방법이다 🙃

• 조건을 만족할 때 까지 이진수를 생성
• 생성한 비트 차이를 카운트하게 되면 n의 자릿수만큼 조사 필요

👎 최악의 경우 약 50자리수의 비트 차이를 N번 검사하게 됨
➡️ 이는 이진수 자리가 커질 수록, 그리고 기준 숫자가 ..111111 로 형태일 경우 악화

 

풀이

기존 숫자보다 큰 수를 변환해 비트 차이를 계산하기보다,
규칙을 발견하여 기존 숫자로부터 비트 차이가 2개 이하인 비트를 생성하는 것이 복잡도를 줄일 수 있다.

[규칙]

자릿수에서 [00, 01, 10] 에 해당하는 경우는 단순히 1을 더해주게 되면 [01, 10, 11] 로 바뀌어 가장 작은 차로 바꿀 수 있다.

문제가 되는 상황은 ..1111 형태를 만났을 때인데,
이 경우도 위 규칙을 적용하여 01111 와 같이 10111 로 바꾸어 주면 가장 작은 차로 탐색을 마칠 수 있다.
즉 작은 자릿수에서 높은 자릿수로 제시한 케이스[00, 01, 10] 와 일치하는지 조사하여 변환 해주면 된다.

1. 마지막 자릿수가 00, 01의 경우 (...00, ...01)는 먼저 리턴해주고
2. 마지막 자릿수가 11인 경우에는 [00, 01, 10] 케이스가 발견까지 높은 자리수를 향해 탐색
   1. 00, 10으로 시작 할 경우(00111..1, 1011...1)에는 자릿수에 맞추어 01... 을 OR 연산하여 리턴
   2. 01의 경우에는 10으로 변환해 주고, 아래 자리수는 보존
      아래 자리수는 11111로 보장되므로 1을 더해 1100000으로 변환하여  1111을 OR 연산
      ➡️ ex) 1011111 ➡️ 1100000 OR 1111 ➡️ 1101111

 

코드

public long[] solution(long[] numbers) {
    long[] answer = new long[numbers.length];
    int answerIndex = 0;
    for (long n : numbers) {
        long number = createNumber(n);
        answer[answerIndex++] = number;
    }
    return answer;
}

long createNumber(long a) {
    if ((a & 1L) == 0 || (a & 2L) == 0) {
        return a + 1L;
    }
    long move = 1L;
    while (true) {
        if (((1L << move) & a) == 0) { // 00, 10
            return a | (1L << (move));
        } else if (((2L << move) & a) == 0) { // 01
            return (a + 1) | (1L << (move)) - 1;
        }
        move++;
    }
}