Python 배열에서 곱이 k가 되는 하위 배열이 존재하는지 확인하는 방법

양수와 음수가 섞여 있는 배열 nums와 목표값 k가 주어집니다. 이때 원소들의 곱이 정확히 k가 되는 연속된 하위 배열(부분 배열)이 배열 안에 존재하는지 확인해야 합니다.

예를 들어 입력이 nums = [-2,-1,1,3,5,8], k = 6이라면 결과는 True입니다. 하위 배열 [-2, -1, 3]의 곱이 (-2) × (-1) × 3 = 6이기 때문입니다.

풀이 접근 방식

이 문제는 '최대 곱 부분 배열' 문제에서 널리 사용되는 동적 계획법 기법을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 인덱스에서 끝나는 하위 배열 중 곱이 가장 큰 값(maximum)과 가장 작은 값(minimum)을 동시에 추적하는 것입니다. 음수를 만나면 곱셈 과정에서 부호가 뒤바뀌어 최댓값과 최솟값의 역할이 서로 바뀌므로, 이 경우 두 값을 맞바꾸어 처리합니다.

구체적인 절차는 다음과 같습니다.

• minimum과 maximum을 첫 번째 원소인 nums[0]으로 초기화합니다.
• 전체 과정에서의 최대 곱을 저장할 prod_max 역시 nums[0]으로 초기화합니다.
• 두 번째 원소부터 마지막 원소까지 순회하며 다음을 반복합니다.
  • 현재 원소 nums[i]가 음수라면 maximum과 minimum의 값을 서로 교환합니다.
  • maximum은 nums[i]와 maximum * nums[i] 중 더 큰 값으로 갱신합니다.
  • minimum은 nums[i]와 minimum * nums[i] 중 더 작은 값으로 갱신합니다.
  • minimum 또는 maximum이 k와 같다면 True를 반환합니다.
  • prod_max를 prod_max와 maximum 중 더 큰 값으로 갱신합니다.
• 순회가 끝날 때까지 조건을 만족하는 값이 없다면 False를 반환합니다.

아래 예제 코드를 통해 더 자세히 살펴보겠습니다.

예제 코드

def solve(nums, k):
    minimum = nums[0]
    maximum = nums[0]

    prod_max = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            maximum, minimum = minimum, maximum

        maximum = max(nums[i], maximum * nums[i])
        minimum = min(nums[i], minimum * nums[i])

        if minimum == k or maximum == k:
            return True

        prod_max = max(prod_max, maximum)
    return False

nums = [-2,-1,1,3,5,8]
k = 6
print(solve(nums, k))

입력

[-2,-1,1,3,5,8], 6

출력

True