문제
https://school.programmers.co.kr/learn/courses/30/lessons/77885#
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
x가 양수일 때, x와 비트가 1 ~ 2개 다른 수 중 제일 작은 수를 구하여라.
문제를 보고 접근을 "제일 작은 수"에 초점을 맞춰서 생각을 해보자.
그럼 다음 표와 같이 생각할 수 있다.
| x | smallest_bigger_number |
| 0 | 1 |
| 1 | 2 |
| ... | ... |
| 10^15 | 10^15 + 1 |
당연히 제일 작은 수는 하나 큰 수일 것이다.
하지만 문제에서는 비트가 1 ~ 2개만 달라야 한다고 한다.
그럼 0 -> 1, 1 -> 2이 된다. 어찌보면 + 1하는 수와 동일하다고 생각할 수 있다.
근데 7, 15와 같은 수는 어떨까?
1을 더하면 최상위 비트에서 한 칸 옆으로 움직이고, 하위 비트들은 다 0으로 꺼지게 된다.
그럼 문제에서 구하라는 1 ~ 2개만 바뀌는 결과가 되지 않는다.
문제에서 1 ~ 2개만 달라야 한다는 것에 초점을 맞춰보자.
7은 어떤 수가 돼야 할까?
문제에 정답이 나와있으므로 11인데, 왜 인지 생각해보자.
7 => 0b0111
11 => 0b1011
이다.
내가 1 ~ 2개만 달라야 하므로 최상위 비트의 1이 왼쪽에 있는 비트와 교대 된 결과를 볼 수 있다.
그럼 무조건 최상위 비트가 왼쪽 한 칸과 바뀌는 것이 제일 작은 수라고 할 수 있을까?
예를 들어 0b1001(9)이라는 수가 있다고 해보자.
제일 작은 수가 무엇일까?
정답은 0b1010(10)이 된다.
얼추 지금 규칙이 보이기 시작한다. 하나의 예시를 더 보자.
0b1010(10) -> 0b1100(12)
10이 12가 되었다.
위와 같은 예시로 우리는 이런 생각을 할 수 있다.
01 구간이 보일 때 10 으로 바꾸면 되겠다.
근데 맘대로 해당 구간을 설정하면 안 되고 제일 하위 비트에서부터 해당 구간을 찾아주면 된다.
고로 for문을 통하여 01 구간을 찾아서 리턴해주자.
정답코드
'''
'25. 11. 8.(토)
1. x > 0, x와 비트가 1 ~ 2개 다른 수 중 제일 작은 수
일단 제일 작은 수이려면 하나 더 큰 수이면 된다.
하지만 이랬을 경우
7 -> 8
15 -> 16
이랬을 때 비트가 전부 바뀌므로 안된다.
1 ~ 2개만 바뀌려면 제일 뒤에 있는 비트 중에서
01인 구간을 찾고 두개만 바꿔주면 된다.
or 1을 더해주면 된다.
1. 제일 뒤에있는 비트가 0이면 켜주면 제일 작은 수
2. 제일 뒤에있는 비트가 1이면 처음으로 만나는 01 구간에서 바꿔주면 제일 작은 수.
'''
def findSmallestNumber(number: int) -> int:
#1번 조건
if number & 1 == 0:
return number | 1
#2번 조건
for idx in range(1, 52):
if not (number & (1 << idx)):
return (number ^ (1 << idx)) & ~(1 << (idx - 1))
def solution(numbers):
answer = []
for num in numbers:
insert_number = findSmallestNumber(num)
answer.append(insert_number)
return answer
깃허브 : https://buly.kr/31UAFeM
유튜브 :
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 슬라이딩 윈도우 / 두 큐 합 같게 만들기 (0) | 2025.11.12 |
|---|---|
| 프로그래머스 / 정렬 / 가장 큰 수 (0) | 2025.11.12 |
| 프로그래머스 / 구현 / [1차] 프렌즈4블록 (0) | 2025.11.02 |
| 프로그래머스 / 정규표현식, 문자열 / [3차] 파일명 정렬 (0) | 2025.11.01 |
| 프로그래머스 / DP / 2 * n 타일링 (0) | 2025.10.19 |