[프로그래머스] 2개 이하로 다른 비트 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

 

 

 

풀이 해설

그냥 모든 수를 2진수로 바꾸고 비교하면 해당 문제는 풀리지 않는다~!.ㅠ.ㅠㅠ

 

1) 주어진 수가 짝수인 경우

주어진 수를 2진수로 표현하면 끝은 항상 0이 된다.

즉 끝의 비트만 1로바꾸면 비트 1개만 바꾸고 주어진 수보다 큰 수를 구할 수 있다. 끝 비트를 1로 바꾸면 수에 +1한 값과 동일하다.

 

2) 주어진 수가 홀수인 경우

단순히 비트 0인 부분을 1로 바꾸면 한 비트를 바꿔 큰 수를 만들 수 있지만

크면서 가장 작은수가 되어야한다. 어떻게 해야할까? 우측에서부터 읽어 만나는 0이 포인트이다.

 

주어진 수를 2진수로 바꾸는것은 동일하다.

이때 우측에서 좌측 방향으로 0을 찾아 그 위치에 1로 바꾸고 그 위치의 바로 오른쪽 비트를 0으로 바꾸면 된다.

 

 

string bitConvert(int) :  넘어온 값을 비트로 바꿔 문자열 형태로 반환

long long valueConvert(string) : 넘어온 비트 문자열을 값으로 반환

string logic(string) : (주어진 수가 홀수인 경우) 비트 문자열 우측에서 왼쪽으로 0을 찾고 그 위치에 1로 바꾸고 뒤에 수를 0으로 변환

 

 

전체 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

string bitConvert(long long num) {
    string str;
    stack<int> s;
    
    while(1) {
        if(num==0)
            break;
        s.push(num%2);
        num/=2;
    }
    
    while(!s.empty()) {
        str += to_string(s.top());
        s.pop();
    }
    
    return str;
}

long long valueConvert(string str) {
    
    long long value = 0;
    long long num = 1;
    
    for(int i=str.length()-1; i>=0; i--) {
        if(str[i]=='1') {
            value += num;
        }
        num*=2;
    }
    return value;
}

string logic(string str) {
    
    str.insert(0,"0"); // 111과 같은 경우를위해 미리 0111로 변환
    for(int i=str.length(); i>=0; i--) {
        if(str[i]=='0') {
            str[i]='1';
            str[i+1]='0';
            break;
        }
    }
    return str;
}

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(int i=0; i<numbers.size(); i++) {
        
        if(numbers[i]%2==0) { // 짝수
            answer.push_back(numbers[i]+1);
        } else { // 홀수
            string str = bitConvert(numbers[i]);
            str = logic(str);
            answer.push_back(valueConvert(str));
        }
        
    }
    
    return answer;
}