[programmers] 33. 다음 큰 숫자

https://programmers.co.kr/learn/courses/30/lessons/12911

코딩테스트 연습 - 다음 큰 숫자

 

1. Problem

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

 

 

2. Code 

 

(1) 효율성에서 탈락

public static int solution(int n) {
        String s = Integer.toBinaryString(n);
        String[] str = s.split("");
        int[] result = check(str);
        String res = "";
        if(result[0] != -1) {
        	res = s.substring(0,result[0]) + "1";
        	result[2]--;
        	result[1]++;
        	for(int i = 0; i < result[1]; i++) {
        		res += "0";
        	}
        	
        	for(int i = 0; i < result[2]; i++) {
        		res += "1";
        	}
        } else {
        	res += "1";
        	result[2]--;
        	result[1]++;
        	for(int i = 0; i < result[1]; i++) {
        		res += "0";
        	}
        	
        	for(int i = 0; i < result[2]; i++) {
        		res += "1";
        	}
        }
        return Integer.parseInt(res, 2);
    }
	
	public static int[] check(String[] str) {
		int[] result = {-1,0,0}; // check, zero, one
		for(int i = str.length-1; i > 0; i--) {
			if(str[i].equals("0")) {
				result[1]++;
			} else if(str[i].equals("1")) {
				result[2]++;
			}
			
			if(str[i-1].equals("0") && str[i].equals("1")) {
				result[0] = i-1;
				return result;
			} else if(i-1 == 0) {
				if(str[i-1].equals("0")) {
					result[1]++;
				} else if(str[i-1].equals("1")) {
					result[2]++;
				}
			}
		}
		return result;
	}

 

(2)

public static int solutionByChar(int n) {
		char[] strNum = Integer.toBinaryString(n).toCharArray();
		int oneCnt = 0;
		for(int i = 0; i < strNum.length; i++) {
			if(strNum[i] == '1') oneCnt++;
		}
		
		for(int i = n+1; i <= 1000000; i++) {
			int oneTemp = 0;
			
			char[] numTemp = Integer.toBinaryString(i).toCharArray();
			for(int j = 0; j < numTemp.length; j++) {
				if(numTemp[j] == '1') oneTemp++;
			}
			if(oneTemp == oneCnt) return i;
		}
		return n;
	}

 

 

(3)

 

public static int solutionByBit(int n) {
		int bitCnt = Integer.bitCount(n);
		for(int i = n+1; i < 1000000; i++) {
			if(bitCnt == Integer.bitCount(i)) return i;
		}
		return n;
	}

 

 

3. Report

 

(1)

처음 생각했던 방법은 (2)방법이였는데 느릴 것같아서 (1)으로 풀었더니 더 느렸다 ^^..

 

(2)

코드에서 처음엔 split("")로 String배열을 만들고 equals로 비교했더니 효율성에서 실패했다.

char배열로 비교하는게 빠른 것 같다.

 

(3)

다른 사람 풀이를 보고 알게 된 방법.. 

bitCount라는게 있는지 처음 알았다 역시 다른 사람 풀이를 꼭 확인해봐야한다.