Leetcode 1009. Complement of Base 10 Integer

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer n, return its complement

 

한 정수의 2진수 표기법에서 모든 비트 0을 1로 바꾸고 1을 0으로 바꿨을 때 그 결괏값이 정수의 보수이다.

• 예를 들어, 정수 5의 2진수는 101이고 101의 보수는 010이고 010은 정수 2이다.

정수 n가 주어졌을 때 n의 보수를 반환하라.

 

Example 1:

Input: n = 5

Output: 2

Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

5의 2진수는 101, 101의 보수는 010, 010는 정수 2이다.

 

Example 2:

Input: n = 7

Output: 0

Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

7의 2진수는 111, 111의 보수는 000, 000는 정수 0이다.

 

Example 3:

Input: n = 10

Output: 5

Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

10의 2진수는 1010, 1010의 보수는 0101, 0101는 정수 5이다.

 

처음에 패턴을 찾았다, x는 모르는 제곱 숫자이다 하지만 2의 x제곱 중에 n보다 크며 근접한 숫자를 찾고 그다음 1만 빼고 그 숫자에서 n를 빼면 정답이 나온다.

 

예시 1:

5(101)에 가장 근접한 2의 x제곱 숫자는 8(1000)이다 여기서 1을 빼면 7(111)이 되고 5(101)와 OR 연산자로 계산을 하면,

111

101

----

010 !!!!

 

다른 예시들도 똑같은 방법으로 되지만 왠지 안될 것 같아 찜찜해 포기했다 그러나 지금 이 글을 쓰는 동안 호기심에 풀었는데 처음 푼 코드보다 빠르고 100%를 찍었다 둘 다 시간 복잡도가 O(logN)이지만 첫 코드는 사실 O(2logN)이라 그런가 보다, 물론 첫 코드의 시간 복잡도는 엄밀히 O(logN)이다.

 

나는 스택으로 풀기 전 맨 오른쪽 비트가 1이면 answer 정수에 제곱을 하고 0이면 answer에 1을 더하고 비트 왼쪽 쉬프르로 풀려했다.

 

예를 들어 n = 5(101) 정수(비트)

n = 5(101)

answer = 0(0)

 

n = 10(2)

answer = 0(0)

 

n = 1(1)

answer = 1(1)

 

n = 0

answer = 10(1)

 

101의 보수는 10가 맞다.

 

하지만 똑같은 방법으로 n이 1010이거나 011일 때 풀면 아래와 같이 결괏값이 나온다.

1010 => 1010

011 => 001

 

그래서 일단 최적 공간 복잡도 O(1)를 타협하고 스택으로 풀었다.

 

일단 나의 첫 성공 코드다, 물론 아마추어같이 풀었다.

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
       
        Stack<Integer> stack = new Stack<Integer>();
        
        while (n > 0) {
            if (n % 2 == 1) {
                stack.push(1);
            } else {
                stack.push(0);
            }
            
            n >>= 1;
        }
        
        while (!stack.isEmpty()) {
            int val = stack.pop();
            
            if (val == 0) {
                n += 1;
            }
            
            if (!stack.isEmpty()) {
                n *= 2;
            }
        }
        
        return n;
    }
}

시간 복잡도는 n를 계속 2번씩 나누기 때문이다. 예: 5(101) => 2(10) => 1(1) => 0(0) 

공간 복잡도는 n의 비트 수만큼 차지한다 n이 32이라면 stack에 5개 숫자들을 차지한다.

 

코드 설명

일단 만약 입력값이 1010이라면 스택에 1010 오른쪽 비트부터 차례차례 넣는다.

 

스택에 포함된 숫자들.

 

1 <- 맨 위

0

1

0 <- 맨 아래

 

그다음 스택 pop() 함수로 위에 숫자들을 빼내고 빼낸 숫자를 0이면 1로 1이면 0으로 바꾸고 n에 넣는다.

n를 쓰는 이유는 answer라는 변수가 굳이 필요 없기 때문이다, 왜냐하면 스택을 쌓은 뒤 n는 0이 되기 때문이다 (n의 값이 0이면 answer과 다를 바가 없다 물론 가독성을 위해 answer 변수를 쓰는 건 좋은 선택이다).

 

while (!stack.isEmpty())문의 동작을 보면,

 

stack = [0, 1, 0] pop() 한 상태

val = 1             pop()에 반환된 값

n = 0(0)           val이 0이면 1을 추가

n = 0(0)           스택이 비어있지 않으면 n를 2배 시킨다

 

stack = [0, 1]

val = 0

n = 1(1)

n = 2(10)

 

stack = [0]

val = 1

n = 2(10)

n = 4(100)

 

stack = []

val = 0

n = 5(101)

if문에서 스택이 비므로 n를 2배 시키지 않는다.

 

결과 값 = 5

 

 

 

두 번째 성공 코드다, 간결하고 빠르다.

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
 
        int lowestNumWithOneMoreDigitThanN = 1;
        
        while (lowestNumWithOneMoreDigitThanN <= n) {
           lowestNumWithOneMoreDigitThanN *= 2;
        }
                
        return --lowestNumWithOneMoreDigitThanN ^ n;
    }
}

N = n

시간 복잡도: O(logN)

공간 복잡도: O(1)

 

첫 if문은 n이 0이면 1을 반환한다, 만약 if문이 없다면 lowestNumWithOneMoreDigitThanN의 초기 숫자가 1이기 때문에 while문이 실행이 안되어 --1 ^ 0의 결과 값인 반환 값은 0이다.

 

알고리즘 원리는 n과 같은 비트수를 가진 숫자 중 가장 큰 숫자에 XOR(^) 연산자로 계산하면 정답이 나온다.

 

예시: n이 5(101)이면 같은 비트를 수를 가진 숫자 중 가장 큰 숫자는 7(111)이다 111만 찾으면 XOR(^) 연산자로,

   101

^ 111

-------

   010   

101 => 010, 정답이다.

 

하지만 11, 111, 1111 이런 숫자들을 구하는 법을 몰랐지만 1을 2배씩 늘려 n보다 커진 이 숫자에 1만 빼면 가능하다.

 

예를 들어, 101의 보다 한 비트 더 많은 이진법 숫자들은 1000 ~ 1111이다 거기서 가장 낮은 숫자는 1000이다! 그래서 변수 이름이 lowestNumWithOneMoreDigitThanN이다 (아마 이 변수를 x로 하고 상세 설명을 주석으로 다는 게 가독성에 좋을 것 같다).

 

그리고 1000에서 1을 빼면 101과 동일한 비트수를 가진 111을 얻게 된다.

 

코드 실행

예시: n = 5(101)

x = 1 (x를 lowestNumWithOneMoreDigitThanN로 간주)

 

while문으로 x는 5보다 많은 8이 되고 while문에서 나올 것이다 1(1) => 2(10) => 4(100) => 8(1000)  정수(비트)

 

이제 x를 1로 빼면 5와 같은 비트수를 가진다 물론 그 비트들은 다 1이다,

8(1000) - 1(1) = 7(111)

 

   101

^ 111

-------

   010

 

 

다른 예시: n = 3(011)

x = 1

x는 4(100)된다

 

x에서 1을 빼면 (111)

 

   011

^ 111

-------

   100