일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- level1
- smart pointer
- Gold
- trie
- SWEA
- Zenject
- Modern C++
- BOJ
- Project
- Silver
- algoritm
- level3
- C++11
- BFS
- stack
- LEVEL2
- 3D RPG
- Unity
- Bronze
- knapsack Problem
- PrefixSum
- two pointer
- Euclidean
- effective C++
- programmers
- 프로그래머스
- 8-Puzzle
- algorithm
- binary search
- Greedy
Archives
- Today
- Total
Patrick's Devlog
[프로그래머스/C++] 다음 큰 숫자 본문
1. 개요
https://school.programmers.co.kr/learn/courses/30/lessons/12911
1-1. 설명
자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의된다
- n의 다음 큰 숫자는 n보다 큰 자연수
- n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같음
- n의 다음 큰 숫자는 위의 조건을 만족하는 수 중 가장 작은 수
자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return하는 함수를 완성한다.
1-2. 제한 사항
- n은 1,000,000 이하 자연수
2. 구현
2-1. 풀이
n의 1 개수를 저장한 후 n 다음 숫자부터 시프트 연산을 이용하여 1의 개수를 세아리고 n과 count가 동일할 때 return 해주었다. 다른 사람의 풀이를 보니 bitset의 count로 쉽게 풀 수 있었다.
2-2. 코드
#include <string>
#include <vector>
using namespace std;
int calBin(int n);
int solution(int n) {
int inputCnt = calBin(n);
int result = n + 1, resultCnt;
while (true) {
resultCnt = calBin(result);
if (resultCnt == inputCnt) break;
result += 1;
}
return result;
}
int calBin(int n) {
int count = 0;
while (n > 0) {
if (n % 2 == 1) count += 1;
n >>= 1;
}
return count;
}
'Study > Algorithms Practice' 카테고리의 다른 글
[BOJ/C++] 계단 오르기(2579번) (0) | 2022.10.02 |
---|---|
[BOJ/C++] 1로 만들기(1463번) (1) | 2022.10.01 |
[BOJ/C++] 동전 0(11047번) (0) | 2022.09.26 |
[프로그래머스/C++] JadenCase 문자열 만들기 (3) | 2022.09.25 |
[BOJ/C++] 성적 통계(5800번) (1) | 2022.09.23 |