프로그래머스 코딩테스트 연습 - 다음 큰 숫자(java)

1. 문제 상황

자연수 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. 입출력 예

n	result
78	83
15	23

 

 

 

3. 문제 풀이 (mine...)

import java.lang.Integer;

class Solution {
    public int solution(int n) {
        int answer = 0;
        String binary1 = Integer.toBinaryString(n).replace("0",""); 
        // n의 2진수 중 1만 남김
        
        for(int i=1; answer<=0; i++){
            String binary2 = Integer.toBinaryString(n+i).replace("0",""); 
            // n+i 2진수의 1들
            
            if(binary2.length() == binary1.length()){ 
            // 1의 갯수가 같으면 answer에 자연수 저장
                answer = n+i;
                break;
            }
        }
        
        return answer;
    }
}

 

나는 n을 2진수로 바꾼 후, replace로 1만 남겨서 갯수를 구했다.

그 후, for문을 통해 자연수를 1씩 높이면서 2진수의 1의 갯수를 비교했다.

 

n과 그 다음 자연수의 2진수 1 갯수가 같아지면 answer에 저장하는 방식을 사용했다.

 

다른 사람들의 문제 풀이를 봤는데 신기한게 많아서... 참고..

 

 

 

4. 문제 풀이 (다른 사람 풀이)

▼ 실제 코드 ▼

class TryHelloWorld {
    public int nextBigNumber(int n) {
        int postPattern = n & -n, smallPattern = ((n ^ (n + postPattern)) / postPattern) >> 2;
        return n + postPattern | smallPattern;
    }
    public static void main(String[] args) {
        int n = 78;
        System.out.println(new TryHelloWorld().nextBigNumber(n));
    }
}

 

 

비트 연산을 사용한 부분이 놀랍다.. 배울점..(메모)

 

---

 

 

▼ 실제 코드 ▼

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));
    }
}

 

Integer.bitCount()를 몰랐는데, 간편하게 사용하기 좋은듯.(메모)

 

 

 

5. 문제 풀이 (내 답 업데이트)

import java.lang.Integer;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=1; answer<=0; i++){
            if(Integer.bitCount(n) != Integer.bitCount(n+i)){
                continue;
            }else if(Integer.bitCount(n) == Integer.bitCount(n+i)){
                return n+i;
            }
        }
        
        return answer;
    }
}

bitCount()를 사용했더니 더 간단해졌다..