오늘 한 내용

---

• C++ 코드카타
• 물리 강의 수강
• Ch3 개인 프로젝트

코드카타 문제

---

오늘의 코드카타 문제는 다음과 같다.
프로그래머스(연속된 부분 수열의 합) : https://school.programmers.co.kr/learn/courses/30/lessons/178870

문제를 요약하자면, 오름차순으로 정렬된 시퀀스 중, 부분 수열의 합이 K가 되는 수열의 시작/끝 인덱스를 반환하면 된다.
이때, 경우의 수가 여러 개라면, 수열의 길이가 짧고 시작 인덱스가 작은 수열을 반환하면 된다.

처음 볼땐 솔직히 전혀 감을 못잡았다. 시퀀스 길이가 최대 백 만개면 최대 O(N)의 시간 복잡도를 지녀야 하는데 일일이 부분 수열을 만드는 방법으로는 O(N)이 절대 안나올 것 같기 때문이다.

그래서 시작을 전혀 못해서 키워드만 알고 해보기로 했는데, 바로 "투 포인터"를 사용하는 것이었다.

투 포인터는 2개의 포인터를 조작하여 원하는 결과를 빠르게 얻어내는 탐색 기법이다.
병합 정렬에서 합치는 과정과 유사하게 동작한다.

다음 상황을 살펴보자

여기서 Start/End는 맨 처음 인덱스를 가리키고 있다. 여기서 핵심은 다음과 같다.

• Start ~ End 까지의 원소 합이 K보다 작으면 End를 증가시킨다.
• Start ~ End 까지의 원소 합이 K보다 크면 Start를 증가시킨다.

현재는 1 < 7이므로 End를 증가시키며, End가 2, 3을 가리킬 때도 동일하게 동작한다.

다음은 10 > 7이기 때문에 Start를 증가시켜야 한다. Start가 2를 가리킬 때도 동일하게 동작한다.

이 경우에 7 = 7이므로, 현재 Start와 End 값을 반환한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int compare(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second - a.first != b.second - b.first)
    {
        return a.second - a.first < b.second - b.first;
    }
    else
    {
        return a.first < b.first;
    }
}

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    vector<pair<int, int>> answer_list;
    
    int start = 0;
    int end = 0;
    int sum = sequence[0];
    // 둘 중 하나가 크기를 오버하면 종료
    while (start != sequence.size() && end != sequence.size())
    {
        if (sum == k)
        {
            answer_list.push_back({start, end});
            end++;
            sum += sequence[end];
        }
        else if (sum < k)
        {
            end++;
            sum += sequence[end];
        }
        else
        {
            sum -= sequence[start];
            start++;
        }
    }
    
    sort(answer_list.begin(), answer_list.end(), compare);
    
    answer.push_back(answer_list[0].first);
    answer.push_back(answer_list[0].second);
    
    return answer;
}