반응형
250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- c#
- network model
- issac3d
- 2018 kakao
- 프로젝트
- unity
- pcce 기출문제
- 로컬 네트워크 연결
- 최대값과 최솟값
- fabrik ik
- 리플렉션 시스템
- 당구 연습
- 2022 kakao
- 백준
- timelessadventure
- 구현
- 프로그래머스
- pccp 기출문제
- netmode
- Algorithm
- fruitspuzzle
- enetrole
- Unreal Engine
- 2019 kakao
- ai controller
- gameinstancesubsystem
- C++
- unrealengine
- Summer/Winter Coding
- 코딩테스트
Archives
- Today
- Total
LeeTaes 공부노트
[프로그래머스/C++ 문제 풀이] Lv. 2 - 다음 큰 숫자 본문
728x90
반응형
문제 설명
자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.
- 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
- 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
- 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.
자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.
제한 사항
- n은 1,000,000 이하의 자연수 입니다.
입출력 예
입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.
문제 풀이
저는 이번 문제를 보고 바로 비트마스킹을 생각하게 되었습니다.
문제에서 조건은 켜져있는 비트 수가 동일한 최소값을 구하는 것이기에, n + 1의 값부터 순차적으로 값을 증가시키며 해당 비트가 켜져있는지 체크 [num & (1 << i)]하였고, 같은 수의 비트가 켜져있는 값을 찾는 순간 종료되도록 하여 문제를 해결하였습니다.
비트가 켜져있는지 체크하는 방법에 대해 간단히 설명드리자면 다음과 같습니다.
예를들어 숫자 5를 이진수로 변환해보면 1 0 1입니다. 즉, 우측부터 0번째와 2번째 비트가 켜져(1)있는 것을 볼 수 있으며, 이러한 방식을 이용해 켜져(1)있는 비트 수를 체크해주었습니다.
정답 코드
더보기
풀이 시간 : 8m 44s
#include <string>
#include <vector>
using namespace std;
// n을 2진수로 변환한 결과 1의 숫자 저장용 변수(켜져있는 비트 수)
int oneCnt;
bool CheckNum(int num)
{
int cnt = 0;
// num의 켜져있는 비트 수를 체크합니다.
for (int i = 0; i <= 20; i++)
{
if (num & (1 << i))
{
cnt++;
}
}
return (oneCnt == cnt);
}
int solution(int n) {
int answer = 0;
// 입력받은 n의 켜진 비트 수를 체크합니다.
for (int i = 0; i <= 20; i++)
{
if (n & (1 << i))
{
oneCnt++;
}
}
int num = n + 1;
// n + 1부터 값을 증가시키며 켜져있는 비트 수가 같은 최소값을 구해주도록 합니다.
while(true)
{
if (CheckNum(num))
{
answer = num;
break;
}
else
{
num++;
}
}
return answer;
}
728x90
반응형
'코딩테스트 > 프로그래머스 (Lv. 2)' 카테고리의 다른 글
[프로그래머스/C++ 문제 풀이] Lv. 2 - 짝지어 제거하기 (0) | 2024.08.24 |
---|---|
[프로그래머스/C++ 문제 풀이] Lv. 2 - 피보나치 수 (0) | 2024.08.23 |
[프로그래머스/C++ 문제 풀이] Lv. 2 - 숫자의 표현 (0) | 2024.08.23 |
[프로그래머스/C++ 문제 풀이] Lv. 2 - 이진 변환 반복하기 (0) | 2024.08.23 |
[프로그래머스/C++ 문제 풀이] Lv. 2 - JadenCase 문자열 만들기 (0) | 2024.08.19 |