어떤 수의 이진 표현을 요소로 담고 있는 배열 n이 주어졌을 때, 결정적 유한 오토마타(DFA)를 이용해 해당 수가 3으로 나누어 떨어지는지 확인하는 문제입니다.
예를 들어 입력이 n = [1, 1, 0, 0](십진수 12의 이진 표현)이라면, 12는 3의 배수이므로 출력은 True가 됩니다.
DFA 접근 방식의 핵심 원리
이 문제의 해결 아이디어는 매우 직관적입니다. 어떤 수가 3으로 나누어질 때 나머지는 반드시 0, 1, 2 중 하나이기 때문에, 각 나머지 값에 대응하는 세 개의 상태를 만들면 됩니다.
여기서 중요한 점은 초기 상태가 곧 최종(final) 상태라는 것입니다. 모든 비트를 읽고 난 후 상태가 0(나머지 0)에 머물러 있다면 그 수는 3의 배수라는 의미이기 때문입니다.
상태 전이는 다음 수학적 원리에 기반합니다. 왼쪽에서 오른쪽으로 비트를 하나씩 읽을 때마다 지금까지의 값은 '기존 값 × 2 + 새 비트'가 되므로, 나머지는 (기존 나머지 × 2 + 비트) mod 3로 갱신됩니다.
- 상태 0: 0을 읽으면 → 0, 1을 읽으면 → 1
- 상태 1: 0을 읽으면 → 2, 1을 읽으면 → 0
- 상태 2: 0을 읽으면 → 1, 1을 읽으면 → 2
알고리즘 단계
이를 코드로 구현하기 위해 다음 순서로 진행합니다.
- dfa_state를 0으로 초기화합니다.
- 배열의 각 자릿수(digit)를 순회하며 현재 상태에 따라 전이 규칙을 적용합니다.
- dfa_state가 0일 때: digit이 1이면 상태를 1로 변경
- dfa_state가 1일 때: digit이 0이면 상태를 2로, 1이면 상태를 0으로 변경
- dfa_state가 2일 때: digit이 0이면 상태를 1로 변경(1이면 2 유지)
- 모든 자릿수를 처리한 후 dfa_state가 0이면 True, 아니면 False를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작을 확인할 수 있습니다.
def solve(nums):
dfa_state = 0
for i in range(len(nums)):
digit = nums[i]
if dfa_state == 0:
if digit == 1:
dfa_state = 1
elif dfa_state == 1:
if digit == 0:
dfa_state = 2
else:
dfa_state = 0
elif dfa_state == 2:
if digit == 0:
dfa_state = 1
if dfa_state == 0:
return True
return False
n = [1, 1, 0, 0]
print(solve(n))입력
[1, 1, 0, 0]
출력
True
마무리
이 방식의 가장 큰 장점은 시간 복잡도 O(n)으로 입력을 한 번만 순회하면서도 큰 정수를 실제로 변환하거나 나눗셈 연산을 수행하지 않고 3의 배수 여부를 판별할 수 있다는 점입니다. 자릿수가 매우 긴 이진 문자열을 다룰 때 특히 유용한 기법이므로, DFA의 상태 전이 개념과 함께 기억해 두면 좋습니다.