[프로그래머스] - 다음 큰 숫자(C++)

다음 큰 숫자

 

문제 설명

자연수 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

 

시작 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    return answer;
}

 

나의 풀이

#include <string>
#include <vector>

using namespace std;

int totwo(int n)
{
    int cnt = 0;
    while(n != 0)
    {
        if(n % 2 == 1) cnt++;
        n /= 2;
    }
    return cnt;
}

int solution(int n)
{
    int m = totwo(n);
    n++;
    while(totwo(n) != m) n++;
    return n;
}

 

코드 분석

int형의 함수 totwo를 매개변수 n을 가지도록 만들어줍니다. 안에서 int형 cnt를 0으로 초기화하고, while문을 통해 n이 0이 될때까지 돌립니다. while문에서는 if문으로 n을 2로 나눈 나머지가 1이면 cnt를 증가시키고 빠져나와서 n을 2로 나눕니다. while문을 빠져나오면 cnt를 리턴합니다.

 

솔루션 함수에서는 int형 변수 m에 totwo(n) 값을 넣습니다. 이후 n을 증가시키고, while문에서 totwo(n) 이 m과 같아질때까지 n을 증가시킵니다. 마지막에는 n을 리턴합니다.

 

풀이 설명

이 문제가 요구하는 것은 다음 큰 숫자이고, 이에 대한 정의는 문제 조건에 만족하는 수입니다. 문제 조건은 n보다 커야하고, n과 다음 큰 숫자를 2진수로 비교했을때 1의 갯수가 같아야 하며, 두 조건을 만족하는 가장 작은 수여야 합니다. totwo()함수는 2진수로 표현한 수의 1의 개수를 세기 위한 함수입니다.

 

입출력 예 1번으로 코드를 실행시켜 보겠습니다. n으로 78이 입력되었고, m에는 주어진 n값으로 실행되는 totwo()함수 값이 만들어집니다. 78로 totwo()함수를 돌리면, 처음에 78을 2로 나눠서 딱 나머지가 없는 39가 나옵니다. 이러면 cnt는 증가하지않고, n이 0이 될때까지 반복하므로, 2진수로 변환된 수가 1인지 0인지 판단하여 1이면 cnt를 올리는 방식이 됩니다.

 

이렇게 1001110으로 표현된 78은 1의 개수가 4개가 됩니다. m은 4가 되어 다시 솔루션 함수로 돌아오면 n을 증가시켜 79가 됩니다. 다음에 바로 while문을 만나는데, 79로 totwo()를 실행한 값이 m과 같아질 때까지 n을 증가시킵니다. 즉, 수를 1씩 증가시켜가며 2진수로 변환했을 때 1의 갯수를 totwo()함수로 확인하는 과정을 반복하는 것입니다.

 

그렇게 최종적으로 83(1010011)이 조건을 만족하는 수로 나오게 되고, 그 값을 리턴하며 종료됩니다.

 

<NEXT>

오늘은 정답률 74%의 연습문제 "다음 큰 숫자"를 풀어보았습니다. 다음에는 연습문제의 "피보나치 수" 문제를 풀어보도록 하겠습니다. 감사합니다.