[프로그래머스] Lv.2 다음 큰 숫자 (java)

2023.05.02 Complete !

🔈 문제 설명

자연수 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)입니다.

💛 내가 쓴 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        String bin = Integer.toBinaryString(n);
		String next_bin = "";
		// 원래 숫자의 1의 개수
		int cnt = bin.length()-bin.replace("1", "").length();
		// 다음 큰 숫자의 1의 개수
		int next_cnt = 0;
		
		for(int i=n+1; i<=1000000; i++) {
			next_bin = Integer.toBinaryString(i);
			// 1의 개수
			next_cnt = next_bin.length() - next_bin.replace("1", "").length();
			if(cnt == next_cnt) {
				answer = i;
				break;
			}
		}
        return answer;
    }
}

아래는 전에 썼던 풀이인데 아마 while(true)를 써서 효율성 부문에서 시간초과 나지 않았을까 싶다 🤔

class Solution {
    public int solution(int n) {
        int answer = 0;
        int num = n+1;
        String bin1=Integer.toBinaryString(n);
        String bin2=""; // 다음 큰 숫자
        int leng1 = 0, leng2 = 0;
        
        while(true){
            bin2=Integer.toBinaryString(num);
            leng1 = bin1.length()-bin1.replace("1","").length();
            leng2 = bin2.length()-bin2.replace("1","").length(); 
            if(leng1 == leng2) break;
            num ++;
        }
        
        return num;
    }
}

💬 남이 쓴 풀이

import java.lang.Integer;
class TryHelloWorld
{
    public int nextBigNumber(int n)
    {
      int a = Integer.bitCount(n);
      int compare = n+1;
      while(true) {
        if(Integer.bitCount(compare)==a)
          break;
        compare++;
      }
      return compare;
    }
    public static void main(String[] args)
    {
        TryHelloWorld test = new TryHelloWorld();
        int n = 78;
        System.out.println(test.nextBigNumber(n));
    }
}

bitCount라는게 있는지는 몰랐다. 다음에 이런 비슷한 문제가 생기면 활용해봐야지 😃