배열(Array)은 동일한 자료형의 여러 요소를 하나로 묶어 저장하는 자료구조입니다. 여러 값을 한 번에 저장할 수 있다는 장점이 있지만, 사용하기 전에 배열의 길이를 미리 정해야 한다는 특징이 있습니다.
합 배열 퍼즐이란?
합 배열 퍼즐에서는 크기가 n으로 고정된 배열 A1이 주어집니다. 이 문제를 해결하기 위해 S1이라는 새로운 배열을 만들어야 하는데, S1의 각 위치에는 해당 위치의 원소 하나만 제외한 나머지 모든 원소들의 합을 저장합니다.
예를 들어 S1[3]을 계산한다면, 인덱스 3에 해당하는 원소를 제외한 나머지 원소들을 모두 더한 값이 됩니다.
예시
Array A1 = {1,2,3,4,6}
Output S1 = {15,14,13,12,10}
풀이 설명
합 배열을 계산하는 방법은 간단합니다. 원본 배열의 전체 합에서 현재 위치의 원소 값만 빼면 되는데, 직관적으로 이해하기 위해 각 인덱스별로 하나씩 계산해 보겠습니다.
- Sum[0]: 인덱스 0의 원소를 제외한 나머지의 합
Sum[0] = 2 + 3 + 4 + 6 = 15 - Sum[1]: 인덱스 1의 원소를 제외한 나머지의 합
Sum[1] = 1 + 3 + 4 + 6 = 14 - Sum[2]: 인덱스 2의 원소를 제외한 나머지의 합
Sum[2] = 1 + 2 + 4 + 6 = 13 - Sum[3]: 인덱스 3의 원소를 제외한 나머지의 합
Sum[3] = 1 + 2 + 3 + 6 = 12 - Sum[4]: 인덱스 4의 원소를 제외한 나머지의 합
Sum[4] = 1 + 2 + 3 + 4 = 10
이렇게 모든 원소를 계산하면 최종 합 배열은 sum = {15, 14, 13, 12, 10}이 됩니다.
알고리즘
가장 기본적인 접근 방식은 이중 반복문을 사용하는 것입니다.
Step 1 : 크기 n(원본 배열의 크기)인 합 배열 sum[n]을 0으로 초기화한다.
Step 2 : sum[]을 순회하며 다음을 수행한다.
Step 2.1 : sum[i]마다 j → 0부터 n-1까지 반복문을 실행한다.
Step 2.2 : if(i != j) { sum[i] += arr[j]; }
Step 3 : 표준 출력문을 사용하여 합 배열을 출력한다.
이 방법의 시간 복잡도는 O(n²)입니다. 하지만 아래 코드처럼 왼쪽 누적합(leftSum)과 오른쪽 누적합(rightSum)을 활용하면 시간 복잡도를 O(n)으로 줄일 수 있어 더 효율적입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int main() {
int arr[] = { 3, 6, 4, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int leftSum[n], rightSum[n], Sum[n], i, j;
leftSum[0] = 0;
rightSum[n - 1] = 0;
cout<<"The original array is : \n";
for (i = 0; i < n; i++)
cout << arr[i] << " ";
for (i = 1; i < n; i++)
leftSum[i] = arr[i - 1] + leftSum[i - 1];
for (j = n - 2; j >= 0; j--)
rightSum[j] = arr[j + 1] + rightSum[j + 1];
for (i = 0; i < n; i++)
Sum[i] = leftSum[i] + rightSum[i];
cout<<"\nThe sum array is : \n";
for (i = 0; i < n; i++)
cout << Sum[i] << " ";
return 0;
}
실행 결과
The original array is : 3 6 4 8 9 The sum array is : 27 24 26 22 21
코드 동작 원리
위 코드의 핵심은 누적합 활용입니다.
- leftSum[i]: 인덱스 i보다 왼쪽에 있는 모든 원소의 합을 저장합니다.
- rightSum[i]: 인덱스 i보다 오른쪽에 있는 모든 원소의 합을 저장합니다.
- Sum[i]: leftSum[i]와 rightSum[i]를 더하면, 자기 자신을 제외한 전체 원소의 합이 됩니다.
이처럼 누적합(prefix sum) 기법을 사용하면 이중 반복문 없이 선형 시간 안에 문제를 해결할 수 있습니다. 코딩 테스트나 면접에서 자주 등장하는 유형이므로 꼭 익혀두시길 추천합니다.