다음 큰 숫자

유태형·2022년 2월 11일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

9/36

문제

문제 분석

이진수 변환시 1의 갯수가 중요한 문제이다. 이진수로 간단히 바꿀 수 있는 API가 있다면 사용하자!

풀이

초기 풀이

이진수를 나머지 연산(%)으로 직접 구하였다. 또 1의 위치를 여러 가지 경우로 나누어 직접 옮기면서 도저히 답을 구할 수 없었다.

이진수 1의 갯수 구하기

Integer.toBinaryString(10진수)API를 활용하면 10진수를 2진수 문자열로 간단히 바꿀 수 있다.

String bin = Integer.toBinaryString(n);

문자열.toCharArray()API는 이용해 문자열을 문자 배열로 나누어 준다.

char[] array = bin.toCharArray();

함수

	public int countOne(String bin){
        int count = 0;
        char[] array = bin.toCharArray(); //문자 배열
        
        for(char temp:array){
            if(temp == '1') //1이면
                count++; //갯수 추가
        }
        
        return count; //갯수 반환
    }

1의 갯수가 같은 다음 큰 수

처음엔 1의 위치를 옮기고, 자리가 부족하면 자리수를 연장하고 하였으나 로직을 구할 수 없었다. 하지만 10진수를 1씩 증가시켜 가며 1의 갯수를 비교하면 쉽게 구할 수 있다.

2진수로 구하기 보단 10진수로 구하는것이 훨씬 빠르고 쉽다.

for(int i=n+1;;i++){ //다음수 부터
       String temp = Integer.toBinaryString(i);
       int next = countOne(temp); //현재 수의 1의 개수 구하기
       
       if(count == next) //1의 개수가 같으면
           return i; //다음 수
   }

코드

class Solution {
    public int solution(int n) {
        //n의 1의 갯수 구하기
        String bin = Integer.toBinaryString(n);
        int count = countOne(bin);
       
        while(true){
            //더 큰 수의 1의 갯수 구하기
            String str = Integer.toBinaryString(++n);
            int ones = countOne(str);
            //n의 1의 갯수와 더 큰수의 1의 갯수가 같다면 종료
            if(ones == count) break;
        }
        //더 큰 수 반환
        return n;
    }
    //1의 갯수 를 구하는 함수
    public int countOne(String bin){
        int count = 0;
        char[] arr = bin.toCharArray(); //문자열을 문자배열로
        
        for(char chr : arr)
            //1이면 갯수 추가
            if(chr == '1') count++;
        
        return count;
    }
}