조건이 있는 배열 A에서 숨겨진 배열 B를 찾는 C++ 코드

n개의 원소를 가진 배열 A가 주어지고, 같은 크기의 숨겨진 배열 B가 존재한다고 가정해 보겠습니다. B의 원소는 양수일 수도, 음수일 수도 있습니다. 인덱스 i(1 ≤ i ≤ n)마다 다음과 같은 연산이 수행됩니다.

• 먼저 A[i]를 0으로 초기화합니다.
• 그다음 A[i]에 B[i]를 더하고, B[i+1]을 빼고, 다시 B[i+2]를 더하는 식으로 부호를 번갈아 가며 더해 나갑니다.

즉, A[i] = B[i] − B[i+1] + B[i+2] − B[i+3] + … 의 관계가 성립합니다. 목표는 배열 A의 값만으로 숨겨진 배열 B를 역산해 내는 것입니다. 예를 들어 입력이 A = [6, -4, 8, -2, 3]이라면 출력은 [2, 4, 6, 1, 3]이 됩니다.

풀이 접근

핵심 아이디어는 인접한 두 교대 합을 서로 더하는 것입니다. A[i]와 A[i+1]을 더하면 다음과 같이 됩니다.

A[i] + A[i+1] = (B[i] − B[i+1] + B[i+2] − …) + (B[i+1] − B[i+2] + B[i+3] − …) = B[i]

B[i+1] 이후의 항들은 부호가 정반대이므로 모두 상쇄되고 결국 B[i]만 남습니다. 따라서 다음 규칙으로 배열 B를 구할 수 있습니다.

• i가 마지막 인덱스가 아니면 → B[i] = A[i] + A[i+1]
• 마지막 원소는 더해 줄 다음 항이 없으므로 → B[n−1] = A[n−1]

이 방법은 배열을 한 번만 훑으면 되므로 시간 복잡도는 O(n), 추가 공간은 O(1)로 매우 효율적입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
    int n = A.size();
    for (int i = 0; i < n - 1; i++)
        cout << A[i] + A[i + 1] << ", ";
    cout << A[n - 1];
}

int main() {
    vector<int> A = { 6, -4, 8, -2, 3 };
    solve(A);
    return 0;
}

입력

{ 6, -4, 8, -2, 3 }

출력

2, 4, 6, 1, 3

마무리

교대 합으로 정의된 배열 문제는 인접한 두 값을 더해 상쇄되는 항들을 제거하는 것이 핵심입니다. 관계식을 직접 전개해 보면 복잡해 보이는 문제도 선형 시간 안에 아주 간단하게 해결할 수 있습니다.