Lv2_[다음 큰 숫자, C++] 풀이 및 알고리즘 정리 - 프로그래머스

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

2진수의 1의 개수가 동일한 큰 수를 찾아야 합니다.

 

(※ 가독성을 위해 2진수 0b는 생략)

1의 수가 바뀌지 않고 다음 큰 숫자를 구하는 방법은 아래와 같다.

• 1(01) + 1(01) = 2(10)

1(01) 위치에 1(01)을 더하면 1의 숫자 개수도 같고 다음 큰 수의 만족을 하는 2(10)의 값을 구할 수 있습니다.

ex) 9(1001)은 1번째 자리에서 일치

• 9(1001) + 1(01) = 10(1010)

ex) (10010)은 2번째 자리에서 일치

• 12(10010) + 2(010) = 14(10100)

 

1(01)로 시작하는 위치를 찾아서 1(01)을 더한다는 개념으로 출발해보자

알고리즘

1) (현재값 & 01) == 01과 일치하는가?

   1-1)일치한다면 현재값 + 01을 해준 후 2)수행
   1-2)일치하지 않는다면 왼쪽으로 한칸 shift (현재값 >> 1) 후 1) 반복
      1-2-1) 현재값 & 1 == 1이라면 oneCount++해줌 (oneCount는 재배치에 사용)

2) 왼쪽 shift 한만큼 오른쪽으로 shift 수행 후 oneCount만큼 일의 자리부터 1을 채움

ex) 46(101110) 다음 큰 수는?

1. 왼쪽 shift 3번 후 01과 일치하기 때문에 (현재값 + 01) = 101 + 01 = 110
2. shift과정에서 1의 값은 2개 존재(110 → oneCount : 2)
3. 오른쪽으로 3번 shift, oneCount는 2이므로 011의 값으로 shift되면 완료
   1100 → 11001 → 110011

46(101110) 다음 큰 수는 51(110011)이 됩니다.

 

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    int index = 0;
    int oneCount = 0;
 
    while(n != 0) {
        if((n & 0b11) == 0b01) {
            n = n + 0b01;
            break;
        }
        if((n & 1) == 1) {
            oneCount++;
        }
        n = n >> 1;
        index++;
    }
 
    while(index > 0) {
        n = n << 1;
        if(index == oneCount) {
            n = n + 0b1;
            oneCount--;
        }
        index--;
    }
    
    return n;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓