[프로그래머스] 2개 이하로 다른 비트

Kim Yuhyeon·2022년 5월 24일

cpp 프로그래머스

알고리즘 + 자료구조

목록 보기

49/161

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

문제

알고리즘 접근 방법

짝수일 때, 홀수일 때로 나누어서 접근

짝수

2 == 0010

4 == 0100

6 == 0110

8 == 1000

항상 최하위 비트가 0임을 알 수 있다.
따라서 1만 더해주면 'x보다 크고 비트와 1~2개 다른 수들 중에서 제일 작은 수'라는 조건을 만족한다.

[최상위 비트 , 최하위 비트]

홀수

5 == 0101

7 == 0111

11 == 1011

으로 항상 최하위 비트가 1인 경우인데,

이 경우는 우선 하나씩 수를 늘려가면서 조건을 맞춰봤다.

5(0101) -> 6(0110)

7(0111) -> 11(1011)

11(1011) -> 13(1101)

우선 조건에서 답은 x보다 항상 커야하기 때문에 비트0을 1로 바꿔줘야하는 과정이 필수적이다.

그런데 제일 작은 수를 찾아야 하기 때문에 왼쪽보다 오른쪽에 있는 비트0을 1로 바꾸는 것이

수가 조금 커질 것이다.

이 규칙대로 7을 바꿔보면 7(0111) -> 15(1111)가 된다.

현재 비트는 1개가 다르고, x보다 커야한다는 조건을 만족한다.

하지만 나머지 조건을 보면 우리가 찾아야 하는 답은 이중에 가장 작아야 하고, 우리는 1개의 비트를 더 바꿀 수 있다.

그러면 나머지 1개의 비트를 어떻게 바꿔야 수가 작아질까?

그렇다 이번엔 7(0111)에서 가장 왼쪽에 있는 비트1을 0으로 바꿔주면 수가 많이 작아질 것이다.

이 규칙까지 적용해서 7을 바꿔보면 7(0111) -> 11(1011)으로 조건을 만족하는 가장 작은 수가 된다.

홀수면 가장 마지막에 있는 0을 1로 바꾸고, 그다음 오는 1을 0으로 바꾼다. (2회 변환)

*주의할 점은 10진수 7에 해당하는 111은 앞에 0이 생략되있다는 사실을 생각하며 코딩으로 풀어야 한다.
애초에 0을 넣어주고 계산하는 것이 편하다

풀이

비트가 1인 가장 최상위 비트는 비트가 0인 최하위 비트의 바로 오른쪽에 있으므로.

우리는 비트가 0인 가장 최하위 비트를 구해줄 것이다.

&연산자를 쓰면 두 비트가 모두 1이어야 1이 나오기 때문에 이를 이용하면 구할 수 있을 것 같다.

우선 비트가 0이면 &연산을 아무리 해도 0밖에 나오지 않으므로 비트가 0인 최하위 비트를 1로 만들어줄 것이다.

num ==9일 때

1001에서 최하위 비트인 0을 1로 바꾸려면 1을 더하면 된다.

그러면 10(1010)이 되고 10(1010)의 보수를 구하는 -연산을 하면

0110이 된다.

이 0110과 10(1010)을 &연산 하면 0010로 즉 비트가 0인 최하위 비트를 알 수 있다.

이 0010을 lastbit이라고 하면 이를 이용해서

비트가 0인 최하위 비트는 1로 바꿔주고 // num | lastbit == 1011

비트가 1인 최상위 비트는 0으로 바꿔준다 // (num | lastbit) &(~(lastbit>>1))

#include <string>
#include <vector>

using namespace std;

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{
           long long lastbit = (numbers[i]+1) & -(numbers[i]+1);
            answer.push_back((numbers[i]|lastbit) & (~(lastbit>>1)));
        }
    }
    return answer;
}