문제 개요
양의 정수 n이 주어졌을 때, n의 이진수 표현(비트 패턴)에서 연속된 1로 이루어진 각 그룹의 길이가 왼쪽에서 오른쪽으로 오름차순으로 증가하는지 확인하는 문제입니다.
예를 들어 n = 1775라고 가정해 보겠습니다. 1775의 이진수 표현은 11011101111이며, 연속된 1의 개수는 왼쪽부터 차례대로 [2, 3, 4]입니다. 이 수열은 계속 증가하고 있으므로 결과는 True입니다.
해결 접근 방식
이 문제는 숫자를 이진수 문자열로 변환한 뒤 한 비트씩 순회하면서 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- n을 이진수 문자열로 변환하여 각 비트를 리스트에 저장합니다.
- 바로 앞 연속 구간에서의 1 개수(p_cnt)와 현재 진행 중인 구간의 1 개수(c_cnt)를 함께 추적합니다.
- 현재 비트가 1이면 c_cnt를 1 증가시킵니다.
- 현재 비트가 0이고 직전까지 진행 중이던 1의 구간이 있다면 해당 구간이 방금 종료된 것이므로 두 값을 비교합니다. 이때 c_cnt가 p_cnt보다 작으면 조건을 만족하지 않으므로 False를 반환합니다.
- 구간이 종료되면 p_cnt를 c_cnt로 갱신하고 c_cnt를 0으로 초기화한 뒤 다음 비트를 검사합니다.
- 전체 순회가 끝난 후에는 마지막 구간에 대해서도 동일한 조건을 검사하고, 모든 검사를 통과하면 True를 반환합니다.
파이썬 구현 코드
def solve(n):
bits_pattern = bin(n)[2:] # '0b' 접두사를 제거한 이진수 문자열
bit_count = len(bits_pattern)
p_cnt = 0 # 이전 연속 구간의 1 개수
c_cnt = 0 # 현재 연속 구간의 1 개수
i = 0
while i < bit_count:
if bits_pattern[i] == '1':
c_cnt += 1 # 연속된 1의 개수 증가
elif c_cnt > 0: # 연속 구간이 방금 종료된 경우
if c_cnt < p_cnt: # 이전 구간보다 짧으면 실패
return False
p_cnt = c_cnt # 구간 정보 갱신
c_cnt = 0
i += 1
if c_cnt > 0 and c_cnt < p_cnt: # 마지막 구간 검사
return False
return True
n = 1775
print(solve(n))실행 결과
입력
1775
출력
True
동작 과정 분석
입력값 1775에 대해 알고리즘이 어떻게 동작하는지 단계별로 살펴보겠습니다.
- 첫 번째 연속 구간(길이 2): 이전 구간이 없으므로 통과하며 p_cnt는 2가 됩니다.
- 두 번째 연속 구간(길이 3): 3이 이전 값 2보다 크거나 같으므로 통과하며 p_cnt는 3으로 갱신됩니다.
- 세 번째 연속 구간(길이 4): 4가 이전 값 3보다 크므로 통과합니다.
- 문자열이 끝날 때까지 모든 구간이 조건을 만족하므로 최종적으로 True가 반환됩니다.
반대로 111011처럼 앞쪽 구간(길이 3)이 뒤쪽 구간(길이 2)보다 긴 경우에는 False가 반환됩니다.
시간 및 공간 복잡도
이 알고리즘은 입력 숫자의 비트 수에 비례해 전체 비트를 한 번만 순회하므로 시간 복잡도는 O(log n)입니다. 이진수 문자열을 저장하기 위한 공간 역시 O(log n)입니다. 따라서 매우 큰 정수에 대해서도 효율적으로 동작합니다.