[PS] 다음 큰 숫자

About this offer

문제 해결1 가장 무식한 방법은 n+1부터 1'000'000 까지 순회하면서 이진수로 변환했을 때 1의 개수가 같은지 체크해서 반환하는 방법이었고, 그거 제외하곤 마땅한 해법이 떠오르진 않았다. 근데 이게 정?답이었다. 생각해보니 1'000'000이면 이진수로 변환해봤자 2^19승 약 19자리이고, 최악의 케이스인 1부터 100만 까지 20자리를 순회한다고 하더라도 겨우 2000만이기 때문에 브루트포스로 해도 그렇게 오랜 시간이 소모되진 않는다. 소스코드1 #include <string> #include <vector> using namespace std; int CountOne(int num) { int ret = 0; while(num != 0) { if(num % 2 != 0) ret++; num /= 2; } return ret; } int solution(int n) { int answer = 0; int num = CountOne(n); for(int i=n+1; i<1'000'000;++i) { int tmp = CountOne(i); if(num == tmp) { answer = i; break; } } return answer; } 굉장히 찝찝한 풀이고, 더 좋은 풀이가 없을까 하고 다른 사람의 풀이를 보자마자 매우 신기한 템플릿 클래스 하나를 봤다. 해결2 이 풀이는 bitset이라는 템플릿 클래스를 사용했는데, https://en.cppreference.com/cpp/utility/bitset template< std::size_t N > class bitset; 간단하게 설명하면, 표준 논리 연산자(&, |, ^ 등등)로 조작 가능한 N 비트 고정 크기 시퀀스이다. 예를 들어 아래와 같이 사용할 수 있다. bitset<8> bit1; // 00000000 bitset<8> bit2(12) // 00001100 이 함수의 api 중에서 count라는 함수가 있는데, true(1)로 설정된 비트 개수를 반환해주는 치트키 기능이 있다. 즉, 원래 n의 1의 개수(이하 num)를 구하고, ++n의 bitset count값이 num과 같은지만 체크하면 된다. 소스코드2 #include <bitset> using namespace std; int solution(int n) { int num = bitset<20>(n).count(); while(bitset<20>(++n).count() != num); return n; } 매우 깔끔하게 코드가 나왔다.

Offer details

Provider

velog

Source

velog-rss

Score

54.39

Confidence

49%