[코딩테스트] 23/12/05 - 연속된 부분 수열의 합 (Level2)

🌜 프로그래머스 링크

문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다. 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
  • 1 ≤ sequence의 원소 ≤ 1,000
  • sequence는 비내림차순으로 정렬되어 있습니다.
• 5 ≤ k ≤ 1,000,000,000
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

문제풀이

• 그냥풀면 시간초과가 발생하는 문제다.
• 투포인터 개념을사용해야 최적화할수있어 통과가 가능하다.

1. for문을 돌려 sequence 사이즈만큼 루프한다.
   • for문의 i는 시작점
2. for문 내의 while문을 돌려서 end점을 찾는다.
3. for문 값을 증가하면서 가장작은 길이(range)를 찾는다.

Github 링크

참고할 문서

투포인터

코드 (C++)

vector<int> solution(vector<int> sequence, int k) {
    int size = sequence.size();
    int maxSum = 0;
    int end = 0;
    int range = size;
    vector<int> answer(2);
    for (int i = 0; i < size; ++i)
    {
        while (maxSum < k && end < size)
        {
            maxSum += sequence[end];
            end++;
        }
        if (maxSum == k && end - 1 - i < range)
        {
            answer[0] = i;
            answer[1] = end-1;
            range = end - 1 - i;
        }
        maxSum -= sequence[i];
    }
    return answer;
}

피드백

처음에는 아래와같이 코드를 구현했는데 바로 시간초과당해버렸다 ㅠ.ㅠ 그덕에 이번에 투포인터 개념을 새로 배웠다

vector<int> solution(vector<int> sequence, int k) {
        vector<int> subAnswer;
        vector<vector<int>> answerList(0); 
        int curSum = 0;
        for (int i = 0; i < sequence.size(); ++i)
        {
            curSum += sequence[i];
            subAnswer.push_back(i);
            while (curSum > k)
            {
                curSum -= sequence[subAnswer[0]];
                subAnswer.erase(subAnswer.begin());
            }
            if (curSum == k)
            {
                answerList.push_back(subAnswer);
            }
        }
        vector<int> answer(2);
        int length = numeric_limits<int>::max();
        for (int i = 0; i < answerList.size(); ++i)
        {
            int temp = answerList[i][answerList[i].size()-1] - answerList[i][0];
            if (temp < length)
            {
                length = temp;
                subAnswer.clear();
                answer[0] = answerList[i][0];
                answer[1] = answerList[i][answerList[i].size()-1];
            }
        }
        return answer;
    }