프로그래머스 : 다음 큰 숫자 [C++]

문제 링크

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

 

문제 설명

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

 

문제 입출력 예)

n	return
78	83
15	23

 

문제 풀이1

• 2진법으로 변환 후 1의 개수를 파악한다.
• n값을 1씩 증가시켜, 초기값 n과 동일한 1의 개수를 가진 숫자를 구한다.

1. 2진법으로 변환 후 1의 개수를 파악하는 함수 작성
2. n값을 1씩 증가시킨다.

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

int two(int n){
    int chCount = 0;
    while(n!=0){
        if(n%2 == 1)
            chCount++;
        n/=2;
    }
    return chCount;
}

int solution(int n) {
    int temp = two(n);
    while(temp != two(n+1))
        n++;
    
    return n+1;
}

정상적으로 실행 되었으나,

비트연산자로 풀이할 수 있다고 하여

비트연산자 풀이 방법을 작성했다.

 

문제 풀이2 - 비트마스크

• 비트연산자 0x01 << i 를 실행 후, n과 and연산을 실시한다.

1. 비트연산자를 통해 1의 개수를 구하도록 한다.
2. n값을 1씩 증가시켜, 초기값 n과 동일한 1의 개수를 가진 숫자를 구한다.

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

int compareN(int n){
    int count=0;
    for(int i=0 ; i < 31 ; i++){
        if(n & (0x01 << i)){
            count++;
        }
            
    }
    return count;
}

int solution(int n) {
    int init = compareN(n);
    while(1){
        n++;
        if(init == compareN(n))
            return n;
    }
}

 

비트마스크란?

알고리즘보다 테크닉에 가까운 기술 중 하나로, 정수의 이진수 표현을 활용한 방법이다.

• 이진수는 0,1만을 가지고 있다.
• true / false 상태를 가진다.
• 십진수로 표현이 가능하다.

a&b	a의 모든 비트와 b의 모든 비트를 AND 연산한다. 둘다 1이면 1, 아니면 0
a|b	a의 모든 비트와 b의 모든 비트를 OR 연산한다. 둘다 0이면 0, 아니면 1
a^b	a의 모든 비트와 b의 모든 비트를 XOR 연산한다. 둘이 다르면 1, 아니면 0
~a	a의 모든 비트에 NOT 연산을 한다. 0이면 1, 1이면 0
a<<b	a를 b비트 만큼 왼쪽으로 시프트한다.
a>>B	a를 b비트 만큼 오른쪽으로 시프트한다.

 

 

리뷰

• 비트마스크를 통한 계산 방법을 많이 풀어봐야겠다.