[프로그래머스/C++] 다음 큰 숫자

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

코딩테스트 연습 - 다음 큰 숫자

다음 큰 숫자

문제

자연수 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 이하의 자연수 입니다.

 

풀이

입출력 예시

 

풀이

막막하다. 매일 10진수의 수들만 보던 사람이, 2진수로 수를 생각해야한다. 물론 2진수 16진수 8진수 등등 배웠고, 계산도 해봤던 사람인 것은 맞지만, 익숙하지 않다는 것은 변함이 없다.

 

처음에는 2진수를 직접 만들어볼까 라는 생각도 들었다. 2진수에서 1의 수를 비교해야하기 때문이다. 하지만 제한 사항에 있는 n은 1,000,000 이하의 자연수라는 말에 이 생각은 바로 접었다.

 

그렇게 풀이를 위한 방법을 검색하던 중, 새로운 클래스를 하나 알게되었다. bitset 클래스이다. 이 클래스의 count 메소드가 비트에서 1의 수를 세어주는 역할을 했다. 이 방법이 있다면 풀이법은 정말 간단했다.

#include <string>
#include <vector>
#include <bitset>
//#include <iostream>

using namespace std;

int solution(int n) {
    //int answer = 0;
    bitset<20> bin_n(n); // 20비트 크기의 2진수로 저장
    size_t n_bit = bin_n.count(); // bin_n에서 1의 수 ex) 15라면 4 반환
    size_t next_bit = 0;
    
    while (n_bit != next_bit) {
        bitset<20> tmp(++n);
        next_bit = tmp.count();
    }
    
    //cout << next_bit << endl; count 메소드 테스트를 위한 테스트 출력
    
    return n;
}

결과