크기가 N인 배열이 있다고 가정해 봅시다. 우리는 이 배열을 곱(product)이 같은 두 개의 하위 배열로 나눌 수 있는 요소를 찾아야 합니다. 그러한 분할이 불가능하다면 -1을 반환합니다.
예를 들어 입력 배열이 [2, 5, 3, 2, 5]라면 결과는 3입니다. 요소 3을 기준으로 배열은 {2, 5}와 {2, 5}라는 두 하위 배열로 나뉘며, 두 배열의 곱은 모두 10으로 동일하기 때문입니다.
문제 해결 접근 방식
이 문제는 접두사 곱(prefix product)과 접미사 곱(suffix product)을 활용하면 효율적으로 해결할 수 있습니다. 각 인덱스를 기준으로 왼쪽 부분의 곱과 오른쪽 부분의 곱을 미리 계산해 두고, 두 값이 일치하는 지점을 찾으면 됩니다.
알고리즘 단계
- n := 배열의 크기
- multiply_pref := 새로운 리스트를 생성하고 array[0]을 삽입
- i를 1부터 n-1까지 반복하며 multiply_pref[i-1] * array[i]를 multiply_pref 끝에 추가 (접두사 곱 계산)
- multiply_suff := 크기가 n인 리스트를 None으로 초기화하고, multiply_suff[n-1]에 array[n-1] 저장
- i를 n-2부터 0까지 1씩 감소시키며 multiply_suff[i+1] * array[i]를 multiply_suff[i]에 저장 (접미사 곱 계산)
- i를 1부터 n-2까지 반복하며 multiply_pref[i]와 multiply_suff[i]가 같은지 확인하고, 같다면 array[i]를 반환
- 조건을 만족하는 요소가 없으면 -1 반환
예제 코드
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def search_elem(array):
n = len(array)
multiply_pref = []
multiply_pref.append(array[0])
for i in range(1, n):
multiply_pref.append(multiply_pref[i-1]*array[i])
multiply_suff = [None for i in range(0, n)]
multiply_suff[n-1] = array[n-1]
for i in range(n-2, -1, -1):
multiply_suff[i] = multiply_suff[i+1]*array[i]
for i in range(1, n-1):
if multiply_pref[i] == multiply_suff[i]:
return array[i]
return -1
array = [2,5,3,2,5]
print(search_elem(array))입력
[2,5,3,2,5]
출력
3
복잡도 분석
이 알고리즘은 배열을 세 번 순회하므로 시간 복잡도는 O(N)입니다. 또한 접두사 곱과 접미사 곱을 저장하기 위해 각각 크기 N의 리스트를 사용하므로 공간 복잡도 역시 O(N)입니다. 단순히 모든 분할 지점마다 곱을 매번 다시 계산하는 O(N²) 방식보다 훨씬 효율적이라는 점이 이 접근 방식의 핵심 장점입니다.