음이 아닌 정수 n이 주어졌을 때, 그 숫자의 이진수 표현에서 가장 긴 연속된 1의 길이를 구하는 문제입니다.
문제 이해하기
예를 들어 입력값이 n = 1469라고 해보겠습니다. 1469의 이진수 표현은 "10110111101"이며, 이 안에는 네 개가 연속된 1이 존재합니다. 따라서 출력 결과는 4가 됩니다.
해결 접근 방법
이 문제는 비트 AND 연산(&)과 왼쪽 시프트 연산(<<)을 활용하면 간단하게 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.
- 카운터 변수 count를 0으로 초기화합니다.
- n이 0이 아닌 동안 다음 과정을 반복합니다.
- n을 n을 왼쪽으로 한 비트 시프트한 값과 AND 연산합니다. 즉, n = n & (n << 1)
- count를 1씩 증가시킵니다.
- 반복이 끝나면 count 값을 반환합니다.
동작 원리
n & (n << 1) 연산을 수행하면, 원래 값과 한 비트씩 밀린 값 사이에 양쪽 모두 1인 인접 비트 위치만 1로 남게 됩니다. 이 연산을 반복할 때마다 연속된 1의 묶음이 하나씩 줄어들고, 결국 모든 비트가 0이 됩니다. 이때 반복이 실행된 횟수가 곧 가장 긴 연속된 1의 길이와 같습니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def solve(n):
count = 0
while n != 0:
n = n & (n << 1)
count = count + 1
return count
n = 1469
print(solve(n))입력
1469
출력
4
복잡도 분석
이 알고리즘의 시간 복잡도는 O(log n)입니다. n의 이진수 자릿수에 비례하여 반복 횟수가 결정되며, 공간 복잡도는 O(1)로 추가 메모리가 거의 필요하지 않아 매우 효율적입니다.