문제 개요
정수 배열 arr과 정수 k가 주어졌을 때, 원본 배열을 k번 반복하여 이어 붙인 새로운 배열을 만든다고 가정해 봅시다. 예를 들어 arr = [1, 2]이고 k = 3이라면, 결과 배열은 [1, 2, 1, 2, 1, 2]가 됩니다.
목표는 이렇게 확장된 배열에서 최대 부분 배열 합(maximum sub-array sum)을 구하는 것입니다. 단, 부분 배열의 길이는 0이 될 수도 있으며, 이 경우 합은 0으로 처리합니다. 또한 정답이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 구해야 합니다.
예를 들어 입력이 [1, -2, 1]이고 k = 5라면, 결과는 2입니다.
해결 접근 방식
배열을 실제로 k번 복사하면 메모리와 시간이 크게 낭비됩니다. 대신 카데인 알고리즘(Kadane's Algorithm)과 접두사·접미사 합을 조합하면 원본 배열을 한 번만 순회해서 답을 구할 수 있습니다. 이를 위해 네 가지 함수를 정의합니다.
1. getKadane() — 최대 부분 배열 합
- ret := -inf, sum := 0으로 초기화합니다(모든 값에 10^9 + 7 모듈로를 적용).
- i를 0부터 배열 크기 - 1까지 순회하며 다음을 수행합니다.
- sum := max(arr[i], arr[i] + sum)
- ret := max(ret, sum)
- 최종 ret이 음수면 0을, 그렇지 않으면 ret을 반환합니다.
2. getSum() — 배열 전체 합
- ret := 0으로 초기화한 뒤(10^9 + 7 모듈로 적용), 모든 원소를 차례로 더해 반환합니다.
3. getPrefix() — 최대 접두사 합
- ret := -inf, sum := 0으로 초기화합니다.
- 왼쪽부터 순회하며 sum := sum + arr[i], ret := max(ret, sum)을 수행합니다.
- ret이 음수면 0을 반환합니다.
4. getSuffix() — 최대 접미사 합
- ret := -inf, sum := 0으로 초기화합니다.
- 배열 끝에서 앞쪽으로 순회하며 sum := sum + arr[i], ret := max(ret, sum)을 수행합니다.
- ret이 음수면 0을 반환합니다.
메인 로직
- kadane := getKadane(arr), sum := getSum(arr), prefix := getPrefix(arr), suffix := getSuffix(arr)를 각각 계산합니다.
- k == 1이면 kadane을 그대로 반환합니다.
- sum > 0이면 max((k - 2) × sum + prefix + suffix, kadane)를 반환합니다. 배열 전체 합이 양수라면 가운데 (k-2)개 복사본을 통째로 포함하는 것이 유리하기 때문입니다.
- 그 외의 경우에는 max(prefix + suffix, kadane)를 반환합니다.
C++ 구현 예시
다음 코드를 통해 구현 과정을 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
int add(lli a, lli b){
return ((a % MOD) + (b % MOD)) % MOD;
}
int mul(lli a, lli b){
return ((a % MOD) * (b % MOD)) % MOD;
}
class Solution {
public:
int getKadane(vector <int>& arr){
int ret = INT_MIN;
int sum = 0;
for(int i = 0; i < arr.size(); i++){
sum = max(arr[i], arr[i] + sum);
ret = max(ret, sum);
sum %= MOD;
ret %= MOD;
}
return ret < 0? 0 : ret;
}
int getSum(vector <int>& arr){
int ret = 0;
for(int i = 0; i < arr.size(); i++){
ret += arr[i];
ret %= MOD;
}
return ret;
}
int getPrefix(vector <int>& arr){
int ret = INT_MIN;
int sum = 0;
for(int i = 0; i <arr.size(); i++){
sum += arr[i];
sum %= MOD;
ret = max(ret, sum);
ret %= MOD;
}
return ret < 0 ? 0 : ret;
}
int getSuffix(vector <int>& arr){
int sum = 0;
int ret = INT_MIN;
for(int i = arr.size() - 1; i >= 0 ; i--){
sum += arr[i];
ret = max(ret, sum);
sum %= MOD;
ret %= MOD;
}
return ret < 0 ? 0 : ret;
}
int kConcatenationMaxSum(vector<int>& arr, int k) {
int kadane = getKadane(arr);
int sum = getSum(arr);
int prefix = getPrefix(arr);
int suffix = getSuffix(arr);
if(k == 1) return kadane;
if(sum > 0){
return max((int)mul((k-2) , sum) + prefix % MOD + suffix % MOD, kadane);
} else {
return max(add(prefix , suffix), kadane);
}
}
};
main(){
vector<int> v1 = {1,-2,1};
Solution ob;
cout << (ob.kConcatenationMaxSum(v1, 5));
}실행 결과 확인
입력
[1,-2,1] 5
출력
2
복잡도 분석
이 알고리즘은 배열을 각각 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다. k 값이 아무리 커져도 성능에 영향을 받지 않는다는 점이 이 접근 방식의 가장 큰 장점입니다.