[level 2] 2개 이하로 다른 비트 - 77885

문제 링크

성능 요약

메모리: 27.9 MB, 시간: 39.91 ms

구분

코딩테스트 연습 > 월간 코드 챌린지 시즌2

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 12일 18:02:58

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	`000...0010`
3	`000...0011`	1

f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	`000...0111`
8	`000...1000`	4
9	`000...1001`	3
10	`000...1010`	3
11	`000...1011`	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 10¹⁵

입출력 예

numbers	result
`[2,7]`	`[3,11]`

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이

소요시간 1시간

long long은 64비트 이므로 반복해줌.
첫번째 비트가 0이라면 단순 1만 더해서 푸시
아니라면 AND 연산을 사용해서 mask에 오른쪽으로 시프트하여 0이 될때까지 반복, 만약 0이 나왔다면 그 뒷자리 비트도 1로 설정하여 XOR 연산 적용.

나의 정답 풀이

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

// 뒤에서 계산해서 0이 나온다면 그 값을 1로 바꾸고 뒤에 있는 값은 0으로 바꿔줌.
// 뒤에값이 없거나 0이라면 냅두고 1이라면 0으로 바꿔줌.

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    long long mask = 1;
        
    for(auto n : numbers)
    {
        mask=1;
        for(int i=0;i<64;i++)
        {
            if(i==0 && (n&mask)==0)
            {
                //numbers값에 1만 더해준다.
                answer.push_back(n+1);
                break;
            }
            if((n&mask)!=0)
                mask <<=1;
            
            else
            {          
                long long result = mask + pow(2,i-1);
                answer.push_back(n ^ result);
                break;
            }          
        }    
    }
    
    
    // 1부터 바꾸면 되지
    // mask는 계속 왼쪽으로 shift해줌 
    // and & 연산자 사용 만약 값이 0이 나왔다면 그 뒤에 있는 값과 1을 ^ 연산 해줌.

    
    return answer;
}

programmers 2단계 2개 이하로 다른 비트