2024. 1. 26. 16:06ㆍ알고리즘_생각하기/프로그래머스 Level 2
문제 설명
자연수 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 이하의 자연수 입니다.
입출력 예nresult
78 | 83 |
15 | 23 |
입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.
풀이
사용 언어 : C++
#include <string>
#include <vector>
using namespace std;
vector<int> ToTwo(int num)
{
vector<int> two;
while(num != 0)
{
if (num % 2 == 1) // 나머지가 1
two.push_back(1);
else // 나머지가 0
two.push_back(0);
num /= 2;
}
return two;
}
int GetNumberOne(vector<int> numvec)
{
int num = 0;
for(int i = 0; i < numvec.size(); i++)
{
if(numvec[i] == 1)
{
num++;
}
}
return num;
}
int solution(int n) {
int answer = 0;
vector<int> nv = ToTwo(n);
int next = n + 1;
while(true)
{
vector<int> nextv = ToTwo(next);
if(GetNumberOne(nv) == GetNumberOne(nextv))
return next;
else
next++;
}
}
'알고리즘_생각하기 > 프로그래머스 Level 2' 카테고리의 다른 글
프로그래머스 - 의상 (0) | 2024.03.30 |
---|---|
프로그래머스 - 피보나치 수 <level 2> (0) | 2024.02.01 |
프로그래머스 - 올바른 괄호 <Level 2> (1) | 2024.01.26 |
프로그래머스 - 이진 변환 반복하기 <Level 2> (0) | 2024.01.24 |
프로그래머스 - 짝지어 제거하기 <Level 2> (0) | 2024.01.17 |