숫자 num이 주어졌을 때, 이 숫자의 이진 표현에서 연속된 0과 1로 이루어진 각 블록(묶음)의 길이가 모두 동일한지 확인해야 합니다. 단, 숫자 0과 모든 자릿수가 1로만 이루어진 수는 블록을 가진다고 간주하지 않으므로 제외합니다.
예를 들어 입력이 num = 455라고 해보겠습니다. 455의 이진 표현은 111000111이며, 이는 '111', '000', '111'이라는 세 개의 블록으로 나뉘고 각 블록의 길이가 모두 3으로 같습니다. 따라서 출력은 True가 됩니다.
해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- bin_form := num의 이진 문자열 표현
- one_count := 각 블록의 길이를 저장할 새로운 집합(set)
- count := 1로 초기화
- i를 0부터 bin_form의 길이 - 2까지 반복:
- bin_form[i]와 bin_form[i + 1]이 같으면 count를 1 증가
- 다르면 지금까지 센 count를 one_count에 추가하고 count를 1로 초기화
- one_count의 크기가 1이면 모든 블록의 길이가 같다는 의미이므로 True 반환
- 그렇지 않으면 False 반환
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
def solve(num):
bin_form = bin(num).replace("0b", "")
one_count = set()
count = 1
for i in range(len(bin_form)-1):
if bin_form[i] == bin_form[i + 1]:
count += 1
else:
one_count.add(count)
count = 1
if len(one_count) == 1:
return True
return False
num = 455
print(solve(num))입력
455
출력
True
코드 설명
먼저 bin() 함수로 정수를 이진 문자열로 변환한 뒤, 불필요한 '0b' 접두사를 제거합니다. 이후 문자열을 한 번만 순회하면서 연속된 같은 문자의 개수를 세고, 블록이 전환될 때마다 해당 길이를 집합에 저장합니다. 집합에는 중복된 값이 저장되지 않으므로, 최종적으로 집합에 남아 있는 값이 하나뿐이라면 모든 블록의 길이가 동일하다는 뜻입니다. 이 알고리즘의 시간 복잡도는 O(n)(n은 비트 길이)이며, 공간 복잡도 또한 O(n)으로 효율적입니다.