파이썬으로 배열을 두 부분으로 나누어 합의 차이가 n이 되는지 확인하는 방법

정수로 이루어진 배열 input_list가 주어졌을 때, 이 배열을 두 부분으로 나누어 각 부분의 합의 차이가 특정 값 n과 같아지도록 할 수 있는지 확인하는 문제입니다. 여기서 n은 미리 주어진 값입니다.

예를 들어, 입력이 input_list = [9, 2, 5, 6]이고 n = 0이라면, 출력은 "Possible"(가능)이 됩니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 1단계: 배열 전체의 합 list_total을 구합니다.
• 2단계: (list_total - n)을 2로 나눈 나머지가 1이라면, 두 부분의 합 차이가 정확히 n이 될 수 없으므로 "Not Possible"을 반환합니다.
• 3단계: 목표값 val = (list_total - n) / 2를 계산합니다.
• 4단계: 누적합 temp_sum을 0으로 초기화한 뒤, 배열을 순회하면서 요소를 하나씩 더합니다.
• 5단계: 순회 중 temp_sum이 val과 같아지면, 그 지점에서 배열을 나눌 수 있으므로 "Possible"을 반환합니다.
• 6단계: 끝까지 조건이 만족되지 않으면 "Not Possible"을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적입니다. 누적합을 활용하기 때문에 모든 분할 지점을 일일이 검사할 필요가 없습니다.

구현 예제

def solve(input_list, n):
    list_total = sum(input_list)
    # 전체 합과 n의 차이가 홀수면 분할 불가능
    if (list_total - n) % 2 == 1:
        return "Not Possible"
    val = (list_total - n) / 2
    temp_sum = 0
    for i in range(len(input_list)):
        temp_sum += input_list[i]
        # 누적합이 목표값과 같으면 분할 가능
        if temp_sum == val:
            return "Possible"
    return "Not Possible"

input_list = [9, 2, 5, 6]
n = 0
print(solve(input_list, n))

입력

[9, 2, 5, 6], 0

출력

Possible

동작 원리 설명

위 예제에서 배열 [9, 2, 5, 6]의 전체 합은 22입니다. n이 0이므로 목표값 val은 (22 - 0) / 2 = 11이 됩니다. 배열을 순회하며 누적합을 계산하면 9 → 11 → 16 → 22 순으로 진행되고, 두 번째 요소까지의 누적합이 11에 도달하므로 [9, 2]와 [5, 6]으로 나눌 수 있습니다. 두 부분의 합은 각각 11로 동일하며, 차이가 0(n)이므로 "Possible"이 출력됩니다.