다음 큰 숫자

· 문제 설명

자연수 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 이하의 자연수 입니다.

 

· 입출력 예

n	result
78	83
15	23

 

· 입출력 예 설명

입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

 

---

· Thinking 1

그냥 주어진 숫자를 2진수로 바꾸고 1의 갯수 저장

숫자++ 하면서 2진수로 바꾸고 1의 갯수 비교 후 같지 않으면 다시 숫자++의 반복..

 

---

· 완성 코드

import java.util.ArrayList;

class Solution {
 	 public int solution(int n) {
      	int cnt = 0;
		int tempCnt = 0;
		int binaryN = n;
		int num = n;
		int binaryNum = num;
		ArrayList<Integer> binary = new ArrayList<Integer>();
		ArrayList<Integer> temp = new ArrayList<Integer>();
		
		while(binaryN != 0) {
			binary.add(binaryN % 2);
			binaryN /= 2;
		}
		
		for (int i = 0; i < binary.size(); i++) {
			if (binary.get(i) == 1) ++cnt;
		}
		
		while(true) {
			num++;
			binaryNum = num;
			while(binaryNum != 0) {
				temp.add(binaryNum % 2);
				binaryNum /= 2;
			}
			
			for (int i = 0; i < temp.size(); i++) {
				if (temp.get(i) == 1) ++tempCnt;
			}
			
			if(tempCnt == cnt) break;
			
			temp.clear();
			tempCnt = 0;
		}
		
		return num;
  	}
}

너무 복잡해..ㅎ

 

---

· 다른 사람의 풀이

public static int solution(int n) {
	int cnt = Integer.bitCount(n);
	int num = n;
	while(true) {
		num++;
		if (Integer.bitCount(num) == cnt) {
			break;
		}
	}
	
	return num;
}

난 바보야.. 난 진짜 무식해.. 난 삽질 전문가야.

- Integer.bitCount(value) : value의 비트가 1인 개수를 반환

bitCount 함수를 몰랐어 난.. 난 바보야

---

· 문제 출처

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

알고리즘 연습 - 다음 큰 숫자 | 프로그래머스