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

연속된 부분 수열의 합

오름 차순으로 정렬된 수열에서 부분 수열의 합이 k인 가장 짧고 왼쪽에 있는 부분 수열을 찾는 문제이다.
이미 정렬되어 있기 때문에 투 푸인터를 이용하면 쉽게 풀 수 있다.

 

문제 설명

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

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

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

 

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

프로그래머스

 

 

제한 사항

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

 

---

 

 

 

 

 

 

풀이

left, right 두 개의 포인터를 관리한다. 
주어진 수열의 가장 왼쪽(index: 0)의 요소가 주어진 배열의 가장 작은 부분 수열이기 때문에 초기값으로 설정한다.

int left = 0, right = 0;  // 계산할 포인터
int answer_l = 0, answer_r = 0;  // 정답 후보
int diff = 1'000'000;  // 차이 
int sum = sequence[0];  // 총합

 

현재까지의 부분 수열이 주어진 k보다 작으면 right 포인터를 오른쪽으로 옮겨 총합에 더한다. (총합이 커진다)
현재까지의 부분 수열이 주어진 k보다 크면 left 포인터를 오른쪽으로 옮겨 총합에서 뺀다. (총합이 작아진다)
위의 작업을 left 포인터가 right 포인터의 오른쪽으로 넘어가기 전 혹은 right 포인터가 전체 수열의 마지막 요소를 넘어가기 전까지 반복한다. 
left 포인터가 right 포인터의 오른쪽으로 넘어간다는 것은 right포인터가 가리키는 값이 k보다 크다는 뜻이다.(left는 총합이 k보다 크면 움직임)
right 포인터가 수열의 마지막 요소를 넘어간다는 것은 현재까지의 부분 수열이 k보다 작다는 뜻인데 더이상 커질 수 없기 때문에 이후에는 정답이 존재할 수 없다.

총합과 k가 같으면 left와 right의 차이를 계산하여 기존의 조건을 만족하는 답과 비교한 후 설정한다.

while(left <= right && right < sequence.size())
{
    if(sum == k)
    {
        if(diff > abs(right - left))  // 정답 후보와 비교
        {
            answer_l = left;
            answer_r = right;
            diff = abs(right - left);
        }
    }
    
    //포인터 이동
    if(sum < k)
    {
        sum += sequence[++right];
    }
    else
    {
        sum -= sequence[left++];
    }
}

 

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
	int left = 0, right = 0;  // 계산할 포인터
	int answer_l = 0, answer_r = 0;  // 정답 후보
	int diff = 1'000'000;  // 차이 
	int sum = sequence[0];  // 총합
    
	while(left <= right && right < sequence.size())
	{
	    if(sum == k)
	    {
	        if(diff > abs(right - left))  // 정답 후보와 비교
	        {
	            answer_l = left;
	            answer_r = right;
	            diff = abs(right - left);
	        }
	    }
	    
	    //포인터 이동
	    if(sum < k)
	    {
	        sum += sequence[++right];
	    }
	    else
	    {
	        sum -= sequence[left++];
	    }
	}
    
    answer.push_back(answer_l);
    answer.push_back(answer_r);
    
    return answer;
}

---