티스토리 뷰
https://programmers.co.kr/learn/courses/30/lessons/77885
코딩테스트 연습 - 2개 이하로 다른 비트
programmers.co.kr
문제 설명
2개 이하로 다른 비트
양의 정수 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^15
입출력 예
문제 풀이
처음 문제를 봤을때 자연수를 2진수로 만들어 비트를 비교해주면 쉽게 구할 수 있을거라고 생각하고 접근했다.
자연수를 2진수로 변환해서 (7 -> 0111) 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 것이 문제였다.
가장 먼저 떠올린 로직은 해당하는 숫자에 1씩 증가시키며, 증가한 수를 2진수로 바꾸고 두 이진수 비트를 비교하는 것이었다. 파이썬 bin 함수를 쓰게되면 0111이 아닌 111의 형태로 나오게 되는데 비교하는 숫자와 자리수를 맞추기 위해 비교하는 숫자의 길이만큼 최상위 비트에 0을 추가해준다(# 자리 수 맞추기)
2진수는 하위 비트부터 비교해야 하므로 리스트의 마지막 원소부터 비교한다. 원래의 수(bin_num)보다 1 증가한 수(cmp_num)과 다른 비트의 개수를 cnt 변수로 체크하고 cnt가 2개 이하이고 0보다 크면 증가시킨 수(cmp_num)을 추가한다.
그러나 테스트 케이스 10번, 11번이 시간 초과가 발생하여 통과하지 못하였다.
문제의 조건에서 numbers의 최대 값이 10^15이니 1씩 더해가며 탐색하는 경우 시간초과가 발생하는 것이다.
# TC 10,11 시간초과
def solution(numbers):
answer = []
for num in numbers:
if num % 2 == 0:
answer.append(num+1)
continue
bin_num = list(bin(num)[2:])
while True:
num += 1
cmp_num = list(bin(num)[2:])
N = len(cmp_num)
if len(bin_num) != N: # 자리 수 맞추기
diff = N - len(bin_num)
for _ in range(diff):
bin_num.insert(0, '0')
cnt = 0
for i in range(N-1, -1, -1):
if bin_num[i] != cmp_num[i]:
cnt += 1
if cnt <= 2 and cnt != 0:
answer.append(num)
break
return answer
그러므로 비트를 인덱싱하여 검색하는 방법으로는 시간 초과를 해결하지 못하였고, 동아리 내에서 같이 스터디하는 분들의 아이디어를 참고하여 답을 구할 수 있었다.
문제를 해결하는데 가장 핵심인 아이디어는 2진수로 나타낸 비트에서 0의 위치를 판단하는 것이다.
2진수로 나타낸 비트를 3가지의 케이스로 구분할 수 있다.
- 모든 비트가 1인경우
- 마지막 비트가 0인경우 (짝수인 경우)
- 마지막 비트가 1이고, 모든 비트가 1이 아닌 경우 (홀수이면서 모든 비트가 1이 아닌 경우)
우선 1번 경우를 생각해보면 11111111보다 큰 수 이고 비트가 1~2개 다르면서 가장 작은 수는 최상위 비트를 0으로 바꾼 후 최상위 비트의 왼쪽에 1을 추가해준다. 즉 101111111 은 비트를 2번 변경한 수 중 가장 작은 수이다.
2번의 경우에는 마지막 비트가 0이므로 짝수에 해당하는 경우이다. 따라서 마지막 비트만 1로 바꿔주면 비트가 1~2개 다르면서 원래의 수 보다 큰 수 중 가장 작은 수이다.
3번의 경우에는 10000111을 생각해보자. 10000111보다 큰 수 중 비트를 1~2번 변경하기 위해서는 마지막으로 0이 나타난 위치를 찾는다. 마지막으로 0이 나타난 위치를 찾아보면 하위 비트에서 부터 4번째 비트를 찾을 수 있다. 해당 비트를 1로 바꾸고 해당 비트보다 한 자리 아래에 있는 비트를 0으로 바꾸면 답을 찾을 수 있다.
조금 더 케이스를 줄여보면 1, 3번의 경우를 한번에 처리할 수 있다.
모든 케이스를 처리하기 전, 최상위 비트 보다 하나 큰 자리에 0을 추가하고 시작하면 된다.
그렇게하면 자연스럽게 1,3번이 같은 케이스가 되고 보다 간결한 코드를 작성할 수 있다.
생각지도 못했는데 좋은 아이디어였다 ! 역시 다양한 사람들끼리 의견을 주고받으면 좋은 아이디어가 나오는 것 같다.
def solution(numbers):
answer = []
for num in numbers:
bin_num = list(bin(num)[2:])
bin_num.insert(0,'0')
ind = 0
N = len(bin_num)
for i in range(N):
if bin_num[i] == '0':
ind = i
if ind == N-1: # 가장 마지막 원소가 1인 경우
bin_num[ind] = '1'
else:
bin_num[ind] = '1'
bin_num[ind+1] = '0'
# 제곱근 계산
j = 0
res = 0
for i in range(N-1, -1, -1):
if bin_num[i] == '1':
res += 2**j
j+=1
answer.append(res)
return answer
'알고리즘' 카테고리의 다른 글
[프로그래머스] 영어 끝말잇기 - 파이썬 (0) | 2022.02.09 |
---|---|
[프로그래머스] 삼각 달팽이 - 파이썬 (0) | 2022.02.08 |
[프로그래머스] 괄호 회전하기 - 파이썬 (0) | 2022.01.26 |
[프로그래머스] 오픈채팅방 - 파이썬 (0) | 2022.01.25 |
[백준] 6609 : 로또 - Python(파이썬) (0) | 2021.08.21 |
- Total
- Today
- Yesterday
- 프로젝트
- 런칭 페스티벌
- jpa
- Spring
- 백준
- 5주차 회고
- 피움 6주차 회고
- 파이썬
- ZNS SSD
- 네트워크
- 3차 데모데이
- java
- 스프링 부트
- 팀프로젝트
- 8주차 회고
- 2차 데모데이
- 알림기능개선기
- dm-zoned 코드분석
- dm-zoned
- 알림개선기
- 스프링MVC
- 우테코 회고
- CI/CD
- 우테코
- 환경 별 로깅 전략 분리
- 회고
- ZNS
- 스프링 프레임워크
- 피움
- 스프링 Logback
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |