[프로그래머스/C++] 연속된 부분 수열의 합 해설 (주석포함)

문제

---

문제 설명

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

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
• 5 ≤ k ≤ 1,000,000,000

---

 

문제 풀이

---

바로 생각난 로직은 for문을 중첩해서 현재 index를 기준으로 모든 연속된 합을 구하는 것인데

3중 for문이라서 무조건 터질 것 같았다.

 

그럼 누적합을 써서 2중 포문으로 줄이는 것까지 생각했는데

제한사항에 보이는 것처럼 길이가 100만이라서 O(n²)으로만 가도 터진다.

 

결국 투포인터를 써서 중첩 횟수를 줄이는 것 외에는 생각나는 것이 없어서 누적합 + 투포인터로 풀어냈다.

---

코   드

---

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer(2) ;
    vector<int> sum(1) ; //누적합 코드를 간결히하려고 앞에 0을 추가
    
    //누적합 계산
    for(int num : sequence)
        sum.push_back(sum.back() + num) ;
    
    //정답이 무조건 존재하므로 초기 정답 인덱스를 처음부터 끝까지로 지정
    answer[1] = sum.size() ;
    
    //만약 시작 인덱스가 끝 인덱스를 넘어서거나 끝 인덱스가 배열 끝에 도달하면 종료
    for(int sp = 0, ep = 0 ; sp <= ep && ep < sum.size() ;)
    {
    	//현재 누적합이 k보다 크다면 시작 인덱스를 앞으로 당김
        if(sum[ep] - sum[sp] > k)
            sp++ ;
        else
        {
        	//만약 합이 k라면 더 적은 구간을 포함하는 배열의 인덱스를 정답으로 저장
            if(sum[ep] - sum[sp] == k && ep - sp < answer[1] - answer[0])
            {
                answer[0] = sp;
                answer[1] = ep;
            }
            //k보다 작거나 같다면 계속해서 끝지점을 넓혀가며 다시 결과를 탐색
            ep++;
        }
    }
    
    answer[1]-- ;
    return answer;
}

---

느낀점: 생각보다 시간이 오래걸렸다 나는 아직 인덱스 다루는 게 미숙한 것 같다.

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

프로그래머스