문제 개요
숫자로 이루어진 배열이 주어졌을 때, 배열의 요소 중 정확히 하나를 제외한 나머지 모든 요소의 약수가 되는 수 B를 찾아야 합니다. 이때 전체 요소의 최대공약수(GCD)는 1이 아니라는 조건이 주어집니다.
예를 들어 입력이 {8, 16, 4, 24}라면, 출력은 8입니다. 8은 배열에서 4를 제외한 나머지 세 요소(8, 16, 24)를 모두 나눌 수 있기 때문입니다.
해결 접근 방식
이 문제는 접두사(prefix) GCD와 접미사(suffix) GCD 배열을 활용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- prefix[i]: 인덱스 0부터 i까지 요소들의 최대공약수
- suffix[i]: 인덱스 i부터 마지막까지 요소들의 최대공약수
특정 요소 array[i]를 제외한 나머지 요소들의 GCD는 prefix[i - 1]과 suffix[i + 1]의 GCD로 구할 수 있습니다. 이 값이 array[i]를 나누지 못한다면, 그것이 바로 우리가 찾는 답입니다.
알고리즘 단계
- n := 배열의 크기
- n이 1이라면 array[0] + 1을 반환 (하나의 요소만 있으므로 그보다 큰 아무 수나 답이 될 수 있습니다)
- 크기 n인 prefix 배열과 suffix 배열을 0으로 초기화합니다.
- prefix[0] := array[0]으로 설정한 뒤, 인덱스 1부터 n-1까지 prefix[i] := gcd(array[i], prefix[i - 1])로 채웁니다.
- suffix[n - 1] := array[n - 1]으로 설정한 뒤, 뒤에서 앞으로 suffix[i] := gcd(suffix[i + 1], array[i])로 채웁니다.
- 각 인덱스 i에 대해 array[i]를 제외한 나머지 요소들의 GCD(cur)를 계산합니다.
- i == 0이면 cur := suffix[i + 1]
- i == n - 1이면 cur := prefix[i - 1]
- 그 외에는 cur := gcd(prefix[i - 1], suffix[i + 1])
- array[i] % cur != 0이라면 cur을 반환합니다.
- 조건을 만족하는 값이 없으면 0을 반환합니다.
구현 예제 코드
다음 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
from math import gcd
def getDivisor(array):
n = len(array)
if (n == 1):
return (array[0] + 1)
prefix = [0] * n
suffix = [0] * n
prefix[0] = array[0]
for i in range(1, n):
prefix[i] = gcd(array[i], prefix[i - 1])
suffix[n - 1] = array[n - 1]
for i in range(n - 2, -1, -1):
suffix[i] = gcd(suffix[i + 1], array[i])
for i in range(0, n):
cur = 0
if (i == 0):
cur = suffix[i + 1]
elif (i == n - 1):
cur = prefix[i - 1]
else:
cur = gcd(prefix[i - 1], suffix[i + 1])
if (array[i] % cur != 0):
return cur
return 0
array = [8, 16, 4, 24]
print(getDivisor(array))
입력
[8, 16, 4, 24]
출력
8
복잡도 분석
- 시간 복잡도: O(n) — prefix와 suffix 배열을 각각 한 번씩 순회하고, 마지막 검증 단계에서 한 번 더 순회합니다.
- 공간 복잡도: O(n) — prefix와 suffix 두 개의 보조 배열이 필요합니다.
마무리
접두사·접미사 GCD 기법은 "특정 하나의 요소를 제외한 나머지 집합"에 대한 연산을 O(1)에 조회할 수 있게 해주는 강력한 패턴입니다. 이 방법은 GCD뿐만 아니라 곱셈이나 논리 연산 등 다양한 누적 연산 문제에도 응용할 수 있으니 꼭 기억해 두시기 바랍니다.