프로그래머스 Lv.2) 다음 큰 숫자
다음 큰 숫자
코딩테스트 연습 - 다음 큰 숫자
자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니
programmers.co.kr
풀이
Lv2 문제를 풀고 있는 이유는 내 생각보다 생각을 많이 해야하는 문제가 존재하고, 기본을 다시 한 번 되돌아보기 좋기 때문이다. 또한, IDE를 사용하지 않고 문제를 푸는 연습을 하고있어서, 코드가 많이 길어지지 않는 문제들로 먼저 연습하고 있기 때문이다.
아무튼 이 문제를 처음 마주했을 때는 '이건 검색을 해야 알 수 있는 문제다' 였다. 물론 코드를 검색하고 이런 것이 아니라 JAVA에서 숫자를 2진수로 변경할 수 있는 메소드를 기본으로 제공해 줄 것 같았기 때문이다. 검색 결과 Integer에 toBinaryString(int num)이라는 메소드를 통해 제공하고 있었다. 물론 Long도 존재하겠지.. 아무튼, 이 문제는 2진수에 대한 이해도, 알고리즘에 대한 엄청난 이해도 요하지 않았다. 물론 더 효과적이고 짧은 코드를 생각해내자면 어렵겠지만, 문제를 푼다라는 입장에서만 봤을 때는 어렵지 않은 문제였다.
내가 푼 로직은 다음과 같다.
1. 입력받은 숫자 n 다음 자연수부터 1씩 증가하면서 while문을 돈다.
2. 비교대상이 될 숫자가 2진수로 변환했을 때, 입력받은 숫자 n의 2진수와 1의 개수가 같으면 while문을 종료하고 답을 return.
코드
public class NextBigNum_12911 {
private static int solution(int n) {
int cnt = getBinaryCnt(n);
boolean isDone = false;
int answer = n;
while(!isDone) {
if(getBinaryCnt(++answer) == cnt) {
isDone = true;
}
}
return answer;
}
private static int getBinaryCnt(int num) {
int result =0;
String str = Integer.toBinaryString(num);
str = str.replaceAll("[0]", "");
for(int i =0; i< str.length(); i++) {
if(str.charAt(i) =='1') {
result++;
}
}
return result;
}
public static void main(String[] args) {
int n = 78;
System.out.println(solution(n));
}
}