문제 설명
0과 1로만 이루어진 배열 A가 주어졌다고 가정해 보겠습니다. 이때 N[i]는 A[0]부터 A[i]까지의 원소들을 하나의 이진수로 해석한 값, 즉 i번째 접두사(prefix)를 의미합니다. 우리가 구해야 할 것은 불리언(Boolean) 값들의 리스트로, answer[i]는 N[i]가 5로 나누어 떨어질 때만 참(True)이 됩니다.
예를 들어 입력이 [0,1,1,1,1,1]이라면 출력은 [true, false, false, false, true, false]가 됩니다.
풀이 접근 방법
배열 전체를 하나의 큰 이진수로 변환한 뒤, 오른쪽 시프트(>>)를 반복하며 마지막 비트를 하나씩 제거하면 '가장 긴 접두사부터 가장 짧은 접두사까지' 차례대로 검사할 수 있습니다.
- length : 배열 A의 크기
- ans : 길이가 length이고 모든 요소가 False로 초기화된 배열
- number : A의 모든 원소를 이어 붙여 만든 이진수 값
- i를 0부터 length-1까지 반복하면서 다음을 수행합니다.
- number를 5로 나눈 나머지가 0이면 ans[length-i-1]을 True로 설정
- number를 오른쪽으로 1비트 시프트 (number = number >> 1)
- 모든 반복이 끝나면 ans를 반환
오른쪽 시프트는 이진수의 마지막 비트를 버리는 연산이므로, 시프트를 한 번 할 때마다 접두사의 길이가 하나씩 줄어듭니다. 따라서 ans[length-i-1]에는 해당 인덱스에서 끝나는 접두사에 대한 판정 결과가 저장됩니다.
구현 예제
class Solution:
def prefixesDivBy5(self, A):
length = len(A)
ans = [False] * length
number = int("".join(map(str, A)), 2)
for i in range(length):
if number % 5 == 0:
ans[length - i - 1] = True
number = number >> 1
return ans
ob = Solution()
print(ob.prefixesDivBy5([0,1,1,1,1,1]))
입력
[0,1,1,1,1,1]
출력
[True, False, False, False, True, False]
더 효율적인 방법: 나머지만 유지하기
배열이 매우 길어지면 전체를 하나의 정수로 변환하는 방식은 큰 수 연산 비용 때문에 비효율적일 수 있습니다. 대신 왼쪽부터 한 비트씩 읽으며 지금까지의 나머지만 유지하면 O(n) 시간 안에 문제를 해결할 수 있습니다.
class Solution:
def prefixesDivBy5(self, A):
ans = []
remainder = 0
for bit in A:
remainder = (remainder * 2 + bit) % 5
ans.append(remainder == 0)
return ans
새로운 비트가 추가되면 기존 값은 2배가 되고 새 비트가 더해지므로, 나머지 역시 (remainder * 2 + bit) % 5로 갱신하면 됩니다. 이 방식은 입력 크기와 관계없이 일정한 메모리만 사용한다는 장점이 있습니다.