문제 상황
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.
A subarray is a contiguous part of an array.
nums와 k가 주어진다. 가장 작은 길이의 비어있지 않은 subarray를 내라. 그 subarray는 합이 k다. 없으면 -1을 리턴해라.
입력
- 1 <= nums.length <= 105
- 105 <= nums[i] <= 105
- 1 <= k <= 109
출력
과정
순서가 유지되는 subarray를 리턴해야하고 input값은 음수를 끼고있는 배열,
음수는 정렬의 적이다. 원래같으면 그냥 바로 누적값으로 정렬할 수 있는 상태를 만들텐데 음수라 그건 불가능하고.
그럼에도 O(n ^ 2)를 용납하지 않는 크기다. 그렇다면 이전의 조사 상태를 유지해야하는데. 이런 생각을 했다.
1. -을 없애자
-부분이 나오면 오른쪽이 나올때까지 합쳐서 구간합을 만들자. 그러면 정렬상태가 만들어지니 좋지 않을까?
그러나 중간애들이 핸들링이 안돼서 한 범위가 너무 크다는 문제가 생길 수 있어서 배제 - ++++ 단계에서 +로 치환이 되니까 + 중간애들을 쓸 수가 없어지잖아.
2. 모든요소를 양수로 만들자
마찬가지로 정렬 누적합을 만들기 위해서, 그러나 그럼 길이가 길어질떄마다 동적으로 -를 해줘야해서 정렬은 결국 아니다.
어떻게 정렬하는가
이전의 미디엄 문제랑 비슷하게 딜레마가 존재한다. 그럼에도 거기엔 흐름이란게 있었다. 요구하는 상황이 매우 까다롭기 때문에, 오른쪽을 먼저 최대로 고정해놓고. 왼쪽을 한칸씩 움직이며 오른쪽의 위치를 줄이는.
정렬된 상태라면 무조건 오른쪽이 더 커야한다
이걸 노릴 수 있었기 때문에 정렬할 수 있었다.
그렇다면 여기서는 ?
브루트 포스라면 어땠을까?
왼쪽에 index를 기준으로 생각해보면 오른쪽요소는 일단 k가 커질때까지 오른쪽으로 이동해야겠지? 그러다가 이제 다음을 보려고 오른쪽으로 한번 갔어 그런데 오른쪽 요소는 왼쪽으로도 올 수 있음. 왜냐면 -일 수도 있거든 왼쪽이. 그러면 값이 더 커지고 경우에 따라서 왼쪽으로 오게될 수도 있다. 그럼 경우에따라서 O(n)이라고 볼 수 없게 된다.
O(n ^ 2) 이고 문제가 풀리지 않는다.
구간합을 하는데 정렬상태를 내가 직접 만들어간다면?
어느순간 -가 됐고, 그전까지 애들의 총합이 k를 넘지 못했다면 그냥 버리는 전략 그래서 결국정렬된 놈만 남기는 전략
→ 왜 이전략이었냐 subarray이니 만큼 -로 바뀐 순간이 있다면 그 순간의 값들을 모두 가져가버려야한다.
[++] [-] 이있을때 총합이 -로 뒤집힌다면 어차피 오른쪽 입장에선 왼쪽 애를 가져가봤자 쓸모가 없어짐 구하는 값은 최소 인덱스이고, 총합에도움이 되는놈은 아님
[-][+][-] 인경우여서 오른쪽 두개만 가져가서 +를 만들수도 있지않냐? 하지만 그러면 전제에 위배됨. 누적합이라는 생각상 어떤 누적합의 단계도 +였어야함. 그럼 거기서부터 구할 수 있지않을까?
만약에 중간에 넘었었다면? 계속 이진탐색해서 가질수 있는 최소의 인덱스를 찾아나섬
중복이 있을 수도 있으니 항상 upperbound로 찾고
typedef long long ll;
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
vector<vector<ll>> prefixSum {};
int answer = nums.size() + 1;
for (int i = 0; i < nums.size(); i++)
{
ll bf = prefixSum.empty() ? 0 : prefixSum.back()[0];
if (bf + nums[i] < 0)
{
prefixSum.clear();
continue;
}
if (nums[i] < 0)
{
prefixSum.back()[0] += nums[i];
// prefixSum.back()[1]++;
}
else
{
ll lastIndex = prefixSum.empty() ? -1 : prefixSum.back()[1];
prefixSum.push_back({bf + nums[i], lastIndex + 1});
}
if (bf + nums[i] >= k)
{
if (prefixSum.size() > 1)
{
int mx = (int) (*upper_bound(prefixSum.begin(), prefixSum.end(), vector<ll>{bf + nums[i] - k - 1, 0}))[1] - 1;
cout << '\\t' << mx << "입니다"<< '\\t';
int distance = prefixSum.back()[1] - mx - 1;
answer = min(answer, distance);
// cout << distance << '\\n';
}
else
{
answer = 1;
break;
}
}
for (vector<ll> arg : prefixSum)
{
cout << arg[0] << ' ' << arg[1] << '\\t';
}
cout << '\\n';
}
return answer == nums.size() + 1 ? -1 : answer;
}
};
나름의 도전이 담겨있지만 실패했다, 주된 원인은 결국 prefixSum이 정렬이 안된다는걸 눈치채지 못했기 때문. 어떻게든 정렬 상태를 만들려했으나 어째서 실패했냐 정렬이 한번 안되니 여러방법으로 누적을하든 해보려고해도 쉽지 않았다.
typedef long long ll;
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
vector<vector<ll>> prefixSum {};
int answer = nums.size() + 1;
for (int i = 0; i < nums.size(); i++)
{
ll bf = prefixSum.empty() ? 0 : prefixSum.back()[0];
if (bf + nums[i] < 0)
{
prefixSum.clear();
continue;
}
if (nums[i] < 0)
{
prefixSum.back()[0] += nums[i];
prefixSum.back()[1]++;
prefixSum.back()[2]++;
}
else
{
ll lastIndex = prefixSum.empty() ? -1 : prefixSum.back()[1];
prefixSum.push_back({bf + nums[i], lastIndex + 1, 1});
}
if (bf + nums[i] >= k)
{
if (prefixSum.size() > 1)
{
cout << i << " (" << bf + nums[i] - k - 1 << ") \\t";
auto val = upper_bound(prefixSum.begin(), prefixSum.end(), vector<ll>{bf + nums[i] - k - 1, 0});
// 0을 더하는 것
for (vector<ll> arg : prefixSum)
{
cout << arg[0] << ' ' << arg[1] << ' ' << arg[2] << "\\t\\t";
}
cout << '\\n';
int mx = (int) (*val)[1];
if ((*val)[0] > bf + nums[i] - k)
{
mx -= (*val)[2];
}
int distance = prefixSum.back()[1] - mx ;
answer = min(answer, distance);
cout << distance << '\\n';
}
else
{
answer = 1;
break;
}
}
}
return answer == nums.size() + 1 ? -1 : answer;
}
};
혼자서는 세상을 구할 수 없다
결국 문제는 정렬실패였다. 정렬되지 않는 상태를 정렬화 하기 위해서 구간합을 사용했다 그럼에도 -일때 구간합이 안되는 것 같았다.
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
// Initialize result to the maximum possible integer value
int shortestSubarrayLength = INT_MAX;
long long cumulativeSum = 0;
// Min-heap to store cumulative sum and its corresponding index
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<>>
prefixSumHeap;
// Iterate through the array
for (int i = 0; i < n; i++) {
// Update cumulative sum
cumulativeSum += nums[i];
// If cumulative sum is already >= k, update shortest length
if (cumulativeSum >= k) {
shortestSubarrayLength = min(shortestSubarrayLength, i + 1);
}
// Remove subarrays from heap that can form a valid subarray
while (!prefixSumHeap.empty() &&
cumulativeSum - prefixSumHeap.top().first >= k) {
// Update shortest subarray length
shortestSubarrayLength =
min(shortestSubarrayLength, i - prefixSumHeap.top().second);
prefixSumHeap.pop();
}
// Add current cumulative sum and index to heap
prefixSumHeap.emplace(cumulativeSum, i);
}
// Return -1 if no valid subarray found
return shortestSubarrayLength == INT_MAX ? -1 : shortestSubarrayLength;
}
};
뭐가 킥이지?
가장 짧은길이 필요한 정보는? 이 문제를 누적합으로 풀려한 건 합리적인 반응이었다. 그럼에도 문제를 풀지 못한건 누적합의 정렬이 실패했기 때문이었다. 그리고 이 문제는 직접 정렬하는것이 아니었다 다른 자료구조, 가장 작은값을 logn안에 찾을 수 있는 큐나 이진트리가있다. 그리고 한번 적절한 누적합을 찾는다면, 그 값은 의미가 없다 왜 ? 진행방향이 오른쪽 한 방향이기 때문에, 내 다음 요소는 나보다 오른쪽에 있는게 확정이다. 그럼 최소값의 특성상 이 값은 더 비교될 필요가 없어.
나때까지의 누적합이 있을때 내가 발견해야하는건 (나의 누적합 - k) 보다 큰 값이 있는지를 찾아봐
배열안에는 항상 매치된적 없는 값들만 있다는게 보장 됨 같거나 크기만한게 있다면 걔네를 뺀다. 그런데 이미 말했다시피 한번 값으로 성립이 됐다면 더이상 그 요소들은 넣을 필요가 없어진다. 그럼 전부 뺀다.
최대와 최소문제에서 내가 방향성만 만들어 낼 수 있다면 (마치 DP처럼) 가지고 있는 정보의 일부를 버릴 수 있게된다는걸 깨달았다. 문제를 다시 풀고 다음에는 틀리지 않게 하는게 좋을 것 같다.
최종 알고리즘
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
int answer = nums.size() + 1;
long long prefixSum = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> queue;
queue.push({0, -1});
for (int i = 0; i < nums.size(); i++)
{
prefixSum += nums[i];
while(!queue.empty() && prefixSum - queue.top().first >= k)
{
answer = min(i - queue.top().second, answer);
queue.pop();
}
queue.push({prefixSum, i});
}
return answer == nums.size() + 1 ? -1 : answer;
}
};
