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

개요

문제가 정말 간단해서 금방 구현할 수 있었다.

직관적으로, 일단 n을 계속 2로 나눠가면서 n의 이진수 형태를 구해가는 과정에서 1의 개수를 구해놓는다.

그리고, n + 1부터 동일하게 2로 나눠가면서 1의 개수를 구하고, n의 이진수의 1의 개수와 동일한 값이 나올 때까지 반복문을 돌리는 방식을 생각했다.

정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int curcnt = 0, tempn = n;
    while (tempn != 0) {
        int r = tempn % 2;
        tempn = tempn / 2;
        if (r == 1) curcnt++;
    }
    int nextn = n + 1;
    while (1) {
        int nextcnt = 0;
        int tempnextn = nextn;
        while (tempnextn != 0) {
            int r = tempnextn % 2;
            tempnextn = tempnextn / 2;
            if (r == 1) nextcnt++;
        }
        if (curcnt == nextcnt) {
            answer = nextn; break;
        }
        nextn++;
    }
    return answer;
}

다른 정답 코드

다른 사람의 풀이를 보다가, bitset을 이용한 풀이를 발견했다.

'이렇게도 풀 수 있구나..'라는 생각을 하면서 bitset 사용법을 간단하게 익혔다.

#include <string>
#include <vector>
#include <bitset>

using namespace std;

int solution(int n) {
    int answer = 0;
    int cnt = bitset<20>(n).count();
    while(bitset<20>(++n).count() != cnt);
    answer = n;
    return answer;
}

bitset<20>(n) : n을 bitset으로 만들건데, 즉 이진수 형태로 만들건데 20비트짜리로 만들겠다.

count() : bitset에서 1의 개수를 반환하는 함수

즉, bitset<20>(n).count() : n의 이진수 형태에서 1의 개수를 반환!!

 

c.f) int cnt = bitset<20>(n).count()는

      bitset<20>(n) bit;

      int cnt = bit.count(); 로 나눠서 작성할 수도 있다.

 

추가 정보) bitset을 선언할 때 정수 말고도 문자열을 대입할 수도 있다.

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n = 78; // 1001110
	string s = "1001110";
	bitset<20> bit1(n);
	bitset<20> bit2(s);
	cout << bit1 << '\n';
	cout << bit2 << '\n';
	cout << bit1.count() << '\n';
	cout << bit2.count();
	return 0;
}

[출력]

00000000000001001110
00000000000001001110
4
4

 

알아두면 좋을 bitset의 추가적인 함수들

all() : 모든 bit가 1이면 true 반환

any() : 적어도 하나의 bit가 1이면 true 반환

none() : 1이 하나도 없다면, 즉 모든 bit가 0이면 true 반환

size() : bitset의 크기를 반환

to_string() : bitset을 문자열로 변환

깨달은 점

1. 어떤 변수를 처음 선언하여 초기화하는 것을 while문 밖에서 해야 하는지, 안에서 해야 하는지를 잘 신경 써야겠다.

2. bitset이라는 개념을 처음 알게 되었다.