[프로그래머스]Lv2. 다음 큰 숫자

본 페이지는 C++ 독학을 위해 작성한 포스트입니다 풀이과정도 포함되어있지만 문법공부에 대한 비중이 있습니다.
(+  Java언어 내용도 포함되어있습니다. )

 

 

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

프로그래머스

 

 

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. 문제해결 접근

• 찾고자 하는 수는, 반복문을 이용해 숫자를 증가하며 해당 조건( 이진변환수에서 1의 갯수가 일치하는 최소값)에 맞는 수를 찾는다
• 인자를 2진수로 변환하는 함수를 사용한다
  Integer.toBinaryString(n);
• 또다른 for문으로 '1'의 갯수를 검사한다
• 조건에 맞는 수를 찾으면 break로 반복문을 빠져나감으로써, 최소값을 찾는 로직을 작성한다.

• 인자를 이진수로 변환하였을때 true를 갯수를 확인하여 반환하는 함수가 있다.
  Integer.bitCount(n);

3.답안 : [언어 : java ]

class Solution {
    public int solution(int n) {
        
		int n2 = 0;
		
		// int n을 변환하는 함수는? Integer.toBinaryString(n)
		String binary = Integer.toBinaryString(n);
		
		int countA = 0;
		// 2진수 변환 확인
//		System.out.println( binary );
		// 1갯수 확인 반복문
		for (int i = 0; i < binary.length(); i++) {
			if(binary.charAt(i)=='1')countA++;
		}
		System.out.println( countA );
		
		for (int i = n+1; i < 1000000; i++) {
			String binaryB = Integer.toBinaryString(i);
			int countB = 0;

			for (int j = 0; j < binaryB.length(); j++) {
//				System.out.println( binaryB );
				if(binaryB.charAt(j)=='1')countB++;
				
			}
			n2 = i;
			if(countA == countB)break;
		}
		
		System.out.println( n2 );
	    return n2;
    }
}

효율성이 떨어진 코드가 작성된 모양이다. 위의 로직에서 비효율적인 부분을 찾아보도록 한다.

 

검색을 통해 확인해본 바, 해당 코드의 비효율적인 부분은 크게 두가지로 사료된다.

1. 대조하는 숫자에서 1의 갯수를 반복하는 반복문의 조건이 i<1000000 인 부분
2. 2진변환을 String 타입으로 전환하고도, 각자릿수를 뽑아 대조하는 등의 여러 로직이 이중포문으로 반복된다는 점

 

---

 

위의 로직에서 1을 문자열로 변환하여 각 비교를 하는것이 아닌,

인자로 받은 정수를 함수처리하여 1의 갯수를 반환하는

Integer.bitCount()

함수가 있다는것을 확인하였다.

 

https://blog.yevgnenll.me/posts/java-integer-bit-count-function

Java BitCount 주어진 정수에서 true bit의 개수를 찾는 함수

 

bitCount()를 이용한 개선된 코드

class Solution {
    public int solution(int n) {
        int n2 = 0;
		
		int i = n;
		
		int cnt = Integer.bitCount(n);
		
//		System.out.println( cnt );
		
		while(true) {
			// n보다 큰 수를 찾기위해 반복한다.
			i++;
			if( cnt == Integer.bitCount(i) ) break;
			
		}
        
        return i;
    }        
}

아주 간결하고 빠르게 처리할 수 있었다.

4. C++ 답안

c++에서는 이러한 함수가 존재하지 않아 다소 복잡한 코드가 완성되었다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(int n)
{
    int answer = 0;
    int origin = n;

    // n의 이진변환 했을 때 1의 수
    int oneCnt = 1;
    while (origin > 0)
    {
    	// n을 2로 나누어 나머지가 1인 수를 계산하여 1개수를 확인한다
        int temp = origin % 2;
        if (temp == 1) { oneCnt++; }   // 나머지가 1이면 카운팅
        origin /= 2;
    }

    int loop = 0;   // 반복 수
    while (true)
    {
        // 1씩 증가하며 이진화 과정에서 1의 수 찾기
        loop++;
        origin = n;
        origin += loop;
        int target = origin;
        int tempOneCnt = 1;

        while (origin > 0)
        {
            int temp = origin % 2;
            if (temp == 1) { tempOneCnt++; }
            origin /= 2;
        }

        // 1의 수가 같은 것을 찾으면 중단
        if (tempOneCnt == oneCnt) { answer = target; break; }
    }

    return answer;
}