문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • 비내림차순으로 정렬된 수열이 주어진다.
  • 부분 수열의 합이 k인 경우 탐색
    • 만약 여러개인 경우, 길이가 가장 짧은 수열
    • 길이가 동일한 수열이라면, 앞쪽 인덱스



2. 알고리즘 설계

  • 처음에 N^2으로 알고리즘 설계 후 시간초과
  • 핵심은 수열을 더하다가 k값보다 커지면 가장 앞의 수열 값부터 빼주는 것
    • queue



3. 로직

  • queue에 값과 index 누적
  • 누적된 값이 k보다 커지면 가장 앞의 수열 값부터 빼준다.
  • 값이 k와 같으면서 부분 수열의 길이가 더 짧다면, return 값 갱신
int start, end;
queue<pii> q;
int len = 1000001, sum = 0;

for(int i=0; i<sequence.size(); i++) {
  q.push({sequence[i], i});
  sum += sequence[i];

  while(sum > k)
    // k값보다 작거나 같아질 때까지 수열의 앞 부분부터 제거

  if(sum == k && q.size() < len)
    // update
}


4. 전체 코드

#include <vector>
#include <queue

using namespace std;
using pii = pair<int, int>;

vector<int> solution(vector<int> sequence, int k) {
    int start=0, end=0;
    
    queue<pii> q;
    int len = 1000001;
    int sum = 0;
    for(int i=0; i<sequence.size(); i++) {
        q.push({sequence[i], i});
        sum += sequence[i];
        
        while(sum > k) {
            pii cur = q.front();
            q.pop();
            
            sum -= cur.first;
        }
        
        if(sum == k && q.size() < len) {
            start = q.front().second;
            end = q.back().second;
            len = q.size();
        }
    }
    
    return {start, end};
}


5. 소감

  • 처음에 N^2으로 풀어서 시간초과가 발생했는데, 방법이 떠오르지 않았다.
  • 핵심은 값이 k보다 커지면 현재 저장된 부분수열의 가장 앞부분 값부터 빼주는 것이었다.
    • 이게 떠오르지 않았음.
  • 평소 BFS 문제를 자주 풀이해서 queue 사용은 자신이 있었는데, 막상 queue 응용 문제가 나오니 사용할 생각조차 하지 못했다.
  • 갈길이 멀구나…