May LeetCoding Challenge[Day4] - Number Complement

Given a positive integer, output its complement number.

The complement strategy is to flip the bits of its binary representation.

Input: 5
Output: 2

Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. 

 

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, 해당 문제는 5라는 값이 주어졌을 때, 이진 값으로 101이 되는데, 이 때 해당 값의 반대 되는 값을 return하면 된다.

 - 여기서, 해당 값의 반대 되는 값의 단어적 정의는 잘 모르겠고, complement를 봐서는 보수인데, 1의 보수와는 다르게 부호값을 제외한 값을 출력해야한다.

 - 문제로 다시 돌아오면, 101은 111 - 101 에 의해서, 010 이 되어서, 2가 된다.

 - 그러면, 해당 문제가 요구하는 것은 주어진 숫자에 대해 111, 1111과 같은 Math.pow(2, n) -1 의 값을 어떻게 빨리 찾을 것인가에 대해서 물어본다.

 - 만약, 입력되어지는 number에서 2를 계속 나눈다면, O(N)이 될 것인데, 이것은 다소 느릴지 모른다.

 - Integer에서는 주어진 숫자를 binaryString으로 표기하는 메소드가 있는데, Integer.toBinaryString(number)에 의해서 주어진 number에 대해서 빠르게 2진 스트링의 값을 구할 수 있다.

 - 그러면 Math.pow(2, Integer.toBinaryString(number).length) - 1 은 주어진 number에 대한 111의 숫자이고, 해당 수에서 number를 빼면, 정답이 나온다. 

 

2. 알고리즘 작성 중, 어려운 점

 

 - toBinaryString은 정말 O(N)이 아닐까?

 - toBinaryString의 내부 구조는 무엇일까?

 

3. 내가 작성한 알고리즘

 

public int findComplement(int num) {
        //1 -> 1
        //11 -> 3
        //111 -> 7
        //1111 -> 15
        //11111 -> 31
        //Math.pow(2,n) - 1
        //num의 2진수 값을 구하고,
        //2진수 값의 길이 Math.pow(2, length) - 1 - num = result
        String binary = Integer.toBinaryString(num);
        return (int)(Math.pow(2, binary.length()) - 1) - num;
}

 

4. 내가 작성한 알고리즘 결과

 

 

5. toBinaryString()은 이렇게 생겼다.

 

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/lang/Integer.java#l302

jdk8/jdk8/jdk: 687fd7c7986d src/share/classes/java/lang/Integer.java

6. shift 연산자를 사용해보자.

 

class Solution {
    public int findComplement(int num) {
        int cp = 0;
        int input = num;
        while(num > 0){
            num = num >> 1;
            cp = (cp << 1) + 1;
        }
        return cp - input;
    }
}

 

6. 결과

 

짝짝

 

문제 :  https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3319/

Explore - LeetCode