[프로그래머스] 연속된 부분 수열의 합

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    int startIndex = 0;
    int endIndex = 0;
    int sum = sequence[0];
    int length = sequence.size();
    int start = 0;
    int end = 0;
    
    while(endIndex < sequence.size()){
        if (sum == k){
            if(endIndex - startIndex < length){
                start = startIndex;
                end = endIndex;
                length = end - start;
            }
            
            endIndex++;
            sum += sequence[endIndex];
        } else if (sum > k){
            sum -= sequence[startIndex];
            startIndex++;
        } else {
            endIndex++;
            sum += sequence[endIndex];
        }
    }
    
    return { start, end };
}

---

📝 풀이

⭐ 참고 : 2024.02.29 - [코딩테스트/백준] - [백준] 2018번 : 수들의 합 5

[백준] 2018번 : 수들의 합 5

이 문제는 투포인터 알고리즘을 통해 풀었습니다.

 

sum이 k보다 작으면 끝 포인터를 증가시킵니다.

sum이 k보다 크면 시작 포인터를 증가시킵니다.

sum이 k와 같고 길이가 가장 짧은 경우에 start와 end를 수정합니다.

 

이 과정을 끝 포인터가 sequence 마지막에 도착할 때까지 반복합니다.

 

최종적으로 start와 end값을 return 합니다.