📒활용개념

1.진수 변환

간단하면서도 함정에 빠지기 쉬운 문제.

📌문제설명

자연수 n에 대하여 다음 조건을 만족하는 수를 구하여라

• n의 다음 큰 수는 n보다 큰 자연수
• n의 다음 큰 수와 n은 2진수로 변환했을 때 1의 갯수가 같다.
• 위의 조건을 만족하는 수 중 가장 작은 수

ex)
78(1001110)의 다음 큰 숫자는 83(1010011)이다.

📌구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;
	
int origin;											//1의 갯수 저장.
string number="0123456789ABCDEF";

string change (int n){								//진수 변환 + 1의 갯수 파악
    string result;
    origin=0;										//1의 갯수 초기화
    if(n==0){
        return "0";
    }
    else{
        while(n>0){
            result=number[n%2]+result;
            n/=2;
        }
    }
    for(int i=0; i<result.size(); i++){				//1의 갯수 파악
        if(result[i]=='1'){
            origin++;
        }
    }
    return result;
}

int solution(int n) {
    int answer = 0;
    int sum;										//n의 1의 갯수 저장
    string binary;
    string st;
    
    binary=change(n);			
    
    sum=origin;
    
    while(1){
        n++;										//조건 1 만족
        st=change(n);
        
        if(sum==origin){							//조건 2 만족
            answer=n;
            break;
        }
    }
    
    return answer;
}

📌주의점

• 해당 문제의 풀이는 여러가지가 있을 수 있다.
• 시간 복잡도를 해결해야 한다. 코드에 따른 시간복잡도 계산을 할 수 있어야 한다.