[LeetCode] Java - Number Complement ( reverse binary )

5월 챌린지 - 4일차 입니다.

연휴 여서 1~2일차 빼먹고.. 3일차부터 하고 있네요 ㅠㅠ 

 

1. 문제 - Number Complement

 

문제는 다음과 같습니다.

 

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

 

양의 정수가 주어지고 출력은 주어진 수의 complement number로 출력합니다. 

complement strategy는 주어진 양의 정수의 이항 표현을 뒤집는 것이다.

 

그래서 예제를 보면 

The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

5를 이진수로 표현하면 101이고 이것을 0->1, 1->0으로 변경하면 2가 된다.

 

2. 풀이

 

풀이.1 Integer의 BinaryString 변환을 활용하기.

    public int findComplement(int num) {
    	// 2진수로 변경하기
    	String numStr = Integer.toBinaryString(num);
    	// 2진수의 길이 만큼 변경
    	StringBuilder sb = new StringBuilder();
    	for(int i=0; i<numStr.length(); i++) { 
    		sb.append((numStr.charAt(i) == '0' ? 1 : 0));
    	}    	
    	return Integer.parseInt(sb.toString(), 2);
    }

Java에서는 Integer를 BinaryString으로 변경이 가능하고 String에 있는 숫자들을 1->0, 0->1로 변경해서 마지막으로 Integer의 parseInt를 통해 2진수를 10진수로 변경하는 방법으로 풀 수 있습니다.

 

풀이.2 비트 연산 활용하기

    public static int findComplement(int num) {
    	
    	int cp = num;
    	int sum = 0;
    	while(num > 0) {
    		// num의 자리수 만큼 이진수에 1로 채운 숫자를 생성
    		sum = (sum << 1) + 1;
    		// 자리수 확인
    		num >>= 1;
    	}
    	return sum - cp;
    }

비트 연산을 활용하는 방법입니다.

주어진 num의 2진수 자리수만큼 1로 채운 숫자를 생성하고 그 수에 num을 빼서 정답을 출력하는 방법입니다.

풀이1 보다 빠르며 자리수가 n이라면 O(n) 만큼 시간이 걸리는 방법입니다.

 

예를 들면 5의 이진수는 101 이기 때문에 3자리를 모든 채운 111 바로 7를 sum으로 구하고 7-5를 하여 2를 구하는 풀이 방법 입니다.

 

111 - 101 = 010