문제
코드
오답 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; //size of arr
int k; // size of sum
int a; // arr
int res; //result
cin >> n;
cin >> k;
int arr[n];
int sumArr[n] = {0, };
vector<int> v1;
for(int i = 0; i < n; i++){
cin >> a;
arr[i] = a;
for(int j = 0; j <= i; j++){
sumArr[i] += arr[j];
}
}
v1.push_back(sumArr[k-1]);
for(int i = k; i < n; i++){
res = sumArr[i] - sumArr[i-k];
v1.push_back(res);
}
sort(v1.begin(), v1.end());
cout << v1[v1.size()-1];
}
정답 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; //size of arr
int k; // size of sum
int a; // arr
int res = -11111; //result
cin >> n;
cin >> k;
int sumArr[n] = {0, };
for(int i = 1; i <= n; i++){
cin >> a;
sumArr[i] = sumArr[i-1] + a;
}
for(int i = k; i <= n; i++){
res = max(res, sumArr[i] - sumArr[i-k]);
}
cout << res;
}
풀이
처음 오답 코드를 분석하며 메꿔나가는 느낌으로 풀이를 하겠다.
n개의 입력을 받고 k개씩의 합을 구하는 문제이기 때문에 여러 과정을 거치지 않으려면
누적 합이라는 방법을 사용하는 것이 좋아보였다.
예를 들어 index 3과 4의 합을 구하고 싶으면 index 4까지의 총 합에서
index 2까지의 총 합을 빼주면 되는 것이다.
이럴 때 사용하는 것이 누적 합이다.
오답 코드를 떠올린 이유는 입력 값의 배열 1개, 이를 통해 만들 누적 합 배열 1개,
누적 합 배열에서 필요한 값만 꺼내와 만들 vector 1개를 만들어 정렬하여 출력하면 풀릴거라 생각했다.
물론 다양한 테스트 케이스를 통과했지만 문제는 시간초과였다.
배열이 10만까지 입력이 가능하니 이를 2중 for문으로 돌리면 엄청난 시간이 들게 된다는 것을 간과했다.
정답 코드는 2중 for문을 없애고 최대한 효율성을 높이는데 초점을 맞췄다.
처음에 입력 값을 굳이 배열에 안담고 입력한 내용만 가지고 알고리즘을 만들 수 있었다.
그 다음 2중 for문을 없애려고 생각해보니 누적합 배열을 index 1칸 전의 누적합 배열에 현재 입력값을 더하면 누적합이 되는 것이었다. 물론 index가 0일 때 index -1을 더할 수 없으니 시작점을 1로 해줘야 한다는 주의점이 있었다.
vector도 없앨 수 있나 생각해보니 c++ 함수 중에 max라는 함수가 있는데 파라미터를 2개 입력하면 더 큰 값을 출력해주는 함수가 있었다. 이를 이용해 배열에 넣고 정렬하지 않고 바로 값만 꺼내올 수 있었다.
결과
후기
코드가 얼마나 달라질 수 있었는지 느낄 수 있었던 문제였다.
남발해댄 for문이 드디어 시간초과를 초래하기 시작했고 조금 더 효율적인 코드가 무엇인지 고민을 해야하는 문제였다.
쉽지는 않았지만 재미는 있었다.
