[Programmers 알고리즘, C++]#Level2_다음 큰 숫자, bitset, 이진법 변환, cmath 헤더 파일

 

[Programmers 알고리즘, C++]#Level 2_다음 큰 숫자

Programmers 알고리즘 문제 풀이, Level 2_다음 큰 숫자

bitset을 활용한 이진 변환과 cmath 헤더 파일을 활용한 알고리즘

 

---

 

문제

 

풀이

1. bitset을 활용한 이진법 변환

Convert a Decimal to Binary in C++ | Techie Delight

1. 주어진 입력 값은 최대 1,000,000으로, 이진수로 변환하면 최대 20개의 자릿수를 가집니다.
2. bitset을 활용해 10진수에서 2진수로 변환하고, 이를 string으로 다시 변환합니다.

 

2. 규칙 찾기

1. 주어진 입력 값을 2진수로 변환 했을 때, 우리는 마지막 '1'이 나오는 위치를 알아야합니다.
2. 그 후, 마지막 '1'이 나오는 위치 이전에 나오는 가장 가까운 '0'이 나오는 위치 또한 기억합니다.
3. 이 두 개의 위치 사이에 나오는 중간 '1'들의 개수 또한 기억합니다.
4. 마지막 '1'과 가장 가까운 '0'의 위치를 스왑 하고, 중간 '1'들을 모두 0으로 변경합니다. 
5. 마지막으로, string의 뒤에서부터 우리가 기억한 중간 '1'들의 개수만큼 다시 '1'을 삽입해줍니다.
6. 결과적으로, '1'의 개수가 같은 "n"보다 큰 가장 작은 자연수를 구할 수 있겠죠!
7. 이때, 주의할 점은 마지막 '1'의 위치가 0번째 인덱스 일 경우, 새로운 '1'이 추가될 -1번째 인덱스가 필요합니다.

 

코드

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

using namespace std;

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

    const int bin = 20;

    // 1. bitset을 활용한 이진수 변환
    string str = bitset<bin>(n).to_string();

    int ind_1 = -1;
    int ind_0 = -1;
    int cnt_1 = 0;
    bool found = false;
    // 2. 가장 마지막에 위치한 1을 찾아냅니다.
    for (int i = str.size() - 1; i >= 0; i--)
    {
    	// 2-1. 가장 가까운 '0'의 위치
        if (found == true && str[i] == '0')
        {
            str[i] = '1';
            ind_0 = i;
            break;
        }
        // 2-2. 중간 '1'들의 개수와 '0'으로 변경하는 작업
        if (found == true && str[i] == '1')
        {
            str[i] = '0';
            cnt_1++;
        }
        // 2-3. 마지막 '1'의 위치
        if (found == false && str[i] == '1')
        {
            str[i] = '0';
            ind_1 = i;
            found = true;
        }
    }

    // 3. 마지막 '1'위로 가장 가까운 '0'을 찾아서 1로 변경해줍니다.
    string str2 = "1";
    if (ind_0 >= 0)
    {
        str[ind_0] = '1';
        str2 = str;
    }
    else
    {
        str2.append(str);
    }

    // 4. 1 에서 0으로 바꾼 'i' 기준 밑으로 1들을 붙여줍니다.
    for (int i = 0; i < cnt_1; i++)
    {
        str2[str2.size() - 1 - i] = '1';
    }

    // 5. 2진법 -> 10진법
    int power = 0;
    for (int i = str2.size() - 1; i >= 0; i--)
    {
        answer += ((str2[i] - '0') * pow(2, power));
        power++;
    }

    return answer;
}

 

결과 화면

 

* 애써 찾아보진 않았지만, 더 간단한 방법이 분명 존재하겠죠. 다만, 혼자 해결해 보았다는 점에 의의를 두고 싶습니다...