일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 백준 15685
- Spring Boot
- with recursive
- 백준
- Coroutine
- 프로그래머스
- 백준 16719
- 백준 17779
- 백준 17626
- JPA
- MySQL
- spring oauth
- sql 기술면접
- 백준 16236
- java 기술면접
- 백준 19238
- springboot
- spring cloud
- Spring
- 프로래머스
- 백준 16235
- java
- 백준 파이썬
- Kotlin
- JVM
- spring security
- re.split
- 파이썬
- MSA
- 웹어플리케이션 서버
- Today
- Total
시작이 반
[프로그래머스] 2개 이하로 다른 비트(Java 자바) 본문
https://programmers.co.kr/learn/courses/30/lessons/77885#
양의 정수 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의 모든 수 ≤ 1015
입출력 예
numbers | result |
[2,7] | [3,11] |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
class Solution {
public long[] solution(long[] numbers) {
long[] answer = new long[numbers.length];
for(int i = 0; i < numbers.length; i++){
long num = numbers[i];
long num2 = num >> 2;
num2 = num2 << 2;
num2 = num2 | 3;
if(num2 == num){
answer[i] = num + 1;
answer[i] = answer[i] | num;
long temp = ~((answer[i] - num) / 2);
answer[i] = answer[i] & temp;
}else{
answer[i] = num+1;
}
}
return answer;
}
}
핵심 코드, 푸는법:
비트연산 문제이다.
2진수에서 맨뒤에 두자리가 11로 시작하면 연산이필요하다.
그외에는 1만더해주면 된다.
ex)
이진법으로 변환한 수가 101010110001111 일때
여기서 봐야할 부분은 맨뒤의 1이 연속해서 나오는 부분이다.
101010110001111
우선 답은 101010110010111 인데
원래 값에서 이 값을 구하기위해서는 비트연산을 해주면된다.
우선 연속으로 1이 2번이상 나오는지 확인하기 위해 Shift연산을 사용하여 확인한다.
101010110001111 >> 2 -> 1010101100011
1010101100011 << 2 -> 101010110001100
101010110001100 | 11 -> 101010110001111
연산하기 전 값과 같으므로 1이 2번이상 나온다.
이후 답을 구해준다.
원래값 + 1
101010110001111 + 1 -> 101010110010000
원래값 | 계산된값
101010110001111 | 101010110010000
-> 101010110011111
이제 101010110011111 빨간 부분을 0으로 만들어주면 된다.
이를 위해서는 우선 계산된 값에서 기존값을 빼주고 not을 붙인다.
계산된 값 - 원래값
101010110011111 - 101010110001111 -> 000000000010000
~계산된값
-> 111111111101111
그다음 이전에 구했던 101010110011111 값과 & 연산을 한다.
101010110011111 & 111111111101111 -> 101010110010111
'알고리즘 > Programmers' 카테고리의 다른 글
[프로그래머스] 영어 끝말잇기(Java 자바) (0) | 2021.10.13 |
---|---|
[프로그래머스] 삼각 달팽이(Java 자바) (0) | 2021.10.12 |
[프로그래머스] 프렌즈4블록(Java 자바) (1) | 2021.10.08 |
[프로그래머스] 큰 수 만들기(Java 자바) (1) | 2021.09.15 |
[프로그래머스] 가장 먼 노드(Java 자바) (1) | 2021.09.15 |