C++로 세 개의 스택에서 합이 같아지는 최댓값 찾기

양수로만 이루어진 세 개의 스택이 주어져 있다고 가정해 봅시다. 목표는 각 스택에서 맨 위(top) 요소를 제거할 수 있다는 조건 하에, 세 스택의 합이 모두 같아질 수 있는 최댓값을 찾는 것입니다. 스택은 배열로 표현되며, 배열의 첫 번째 인덱스가 곧 스택의 맨 위 요소를 의미합니다.

예를 들어 스택이 [3, 10], [4, 5], [2, 1]처럼 구성되어 있다면 결과는 0이 됩니다. 세 스택의 합(각각 13, 9, 3)을 같게 만들려면 모든 요소를 전부 제거하는 수밖에 없기 때문입니다.

문제 해결 접근법

이 문제의 핵심 아이디어는 매우 직관적입니다. 세 스택의 합을 계속 비교하면서, 합이 서로 같지 않다면 현재 합이 가장 큰 스택에서 맨 위 요소를 하나씩 제거하는 것입니다. 구체적인 단계는 다음과 같습니다.

먼저 각 스택에 있는 모든 요소의 합을 구합니다.
세 스택의 합이 모두 같다면, 그 값이 바로 우리가 찾는 최대 합입니다.
합이 다르다면, 세 스택 중 합이 가장 큰 스택의 맨 위 요소를 제거한 뒤 앞선 두 단계를 다시 반복합니다.

단, 세 스택 중 어느 하나라도 모든 요소가 소진되면 더 이상 합을 일치시킬 수 없으므로 0을 반환합니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

int maxStackSum(int stk1[], int stk2[], int stk3[], int size1, int size2, int size3) {
    int add1 = 0, add2 = 0, add3 = 0;

    // 각 스택의 전체 합 계산
    for (int i = 0; i < size1; i++)
        add1 += stk1[i];
    for (int i = 0; i < size2; i++)
        add2 += stk2[i];
    for (int i = 0; i < size3; i++)
        add3 += stk3[i];

    int top1 = 0, top2 = 0, top3 = 0;

    while (true) {
        // 한 스택이라도 비어 있으면 합을 같게 만들 수 없음
        if (top1 == size1 || top2 == size2 || top3 == size3)
            return 0;

        // 세 스택의 합이 모두 같으면 정답 반환
        if (add1 == add2 && add2 == add3)
            return add1;

        // 합이 가장 큰 스택의 top 요소 제거
        if (add1 >= add2 && add1 >= add3)
            add1 -= stk1[top1++];
        else if (add2 >= add1 && add2 >= add3)
            add2 -= stk2[top2++];
        else
            add3 -= stk3[top3++];
    }
}

int main() {
    int stack1[] = { 3, 2, 1, 1, 1 };
    int stack2[] = { 4, 3, 2 };
    int stack3[] = { 1, 1, 4, 1 };

    int size1 = sizeof(stack1) / sizeof(stack1[0]);
    int size2 = sizeof(stack2) / sizeof(stack2[0]);
    int size3 = sizeof(stack3) / sizeof(stack3[0]);

    cout << "The maximum sum is: " << maxStackSum(stack1, stack2, stack3, size1, size2, size3);
}

출력 결과

The maximum sum is: 5

동작 과정 살펴보기

위 예제에서 세 스택의 초기 합은 각각 8, 9, 7입니다. 알고리즘은 다음 순서로 진행됩니다.

합이 가장 큰 두 번째 스택(9)에서 4를 제거 → 합: 8, 5, 7
이제 첫 번째 스택(8)이 가장 크므로 3을 제거 → 합: 5, 5, 7
세 번째 스택(7)에서 1을 제거 → 합: 5, 5, 6
세 번째 스택(6)에서 1을 한 번 더 제거 → 합: 5, 5, 5
세 스택의 합이 모두 5로 같아졌으므로 최종 결과 5를 반환합니다.

시간 및 공간 복잡도

초기 합 계산에 O(n₁ + n₂ + n₃)의 시간이 소요되며, 이후 각 요소는 최대 한 번씩만 제거되므로 전체 시간 복잡도 역시 O(n₁ + n₂ + n₃)입니다. 인덱스 포인터 몇 개만 추가로 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다.