연속된 부분 수열의 합(V)

문제출처 https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

문제 설명: 비내림차순(중복을 허용하는 오름차순) 수열이 주어질 때 임의의 두 원소와 그 사이의 원소를 모두 포함하는 부분 수열의 합이 k와 같을 때 두 원소의 값을 구하는 문제이다. 투포인터 알고리즘을 활용해야하며 아래의 조건을 만족해야한다.

조건) 합이 k인 부분 수열이 여러개인 경우 길이가 짧은 수열인 두 원소의 값을 찾고, 길이가 짧은 수열이 여러 개인 경우 시작 인덱스가 작은 두 원소의 값을 찾는다.

입출력 예를 통해 두 원소는 sequence의 2개의 인덱스로 이해하면 된다.

 

로직:

1. 투포인터 문제로 두개의 포인터를 사용하여 구해진 부분수열 합(누적 합)이 위 다중 조건에 만족하는 인덱스를 찾아 우선순위 큐에 저장하여 정렬을 한다.

2. 부분수열의 합이 정답인 k보다 작으면 pt2을 +1 증가시키고 증가된 pt2를  sequence[pt2]로 하여 sum에 더한다. 

3. 부분수열의 합이 정답인 k보다 크면 누적합인 sum에서 sequence[pt1] 값을 빼고 pt1을 +1 증가시켜 sequence[pt1]를 sum에 더한다.

4. pt2가 sequence 사이즈와 같아질 때까지 2번과 3번을 반복하며 k와 같은 sum의 pt1, pt2를 찾는다.

#include<bits/stdc++.h>
using namespace std;

// 부분 수열의 합이 k일 때 양 끝 점인 두개의 포인터 저장 용도.
struct node {
    int px1;
    int px2;
    int dist;
};
//다중 조건: 1순위 정렬) 합이 K인 부분 수열 여러개 인 경우 짧은 수열. 2순위 정렬) 길이가 짧은 수열 여러개 일 경우 인덱스 작은 순
bool operator<(node var, node tar) {
    if (tar.dist < var.dist)return 1;
    if (tar.dist > var.dist)return 0;
   return tar.px1 < var.px1;
}
vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    //우선순위 q를 통해 빠른 정렬(heap) 구현
    priority_queue<node> q;
    // 투포인터 구현 위한 변수 선언
    //pt1 좌측 끝점 포인터, pt2 우측 끝점 포인터  (투포인터)
    int pt1 = 0;
    int pt2 = 0;
    int sum = sequence[0];
    while (1) {
        if (pt1 == pt2) sum = sequence[pt1];
        if (sum < k) { // sum이 작으면 pt2를 증가시켜서 sum에 sequence의 pt2인덱스의 값을 더함.
            if (pt2 == 5) {
                cout << 1;
            }
            pt2++;
            if (pt2 == sequence.size())break; // range out 방지.
            sum += sequence[pt2];
        }
        else if (sum > k) { // sum이 크면 pt1을 인덱스로 가진 sequence배열의 값을 빼주고 pt1을 증가시킴./ 
            sum -= sequence[pt1];
            pt1++;
        }
        else { // sum == k 인 경우
            q.push({ pt1, pt2, pt2 - pt1 }); // 힙정렬
            sum -= sequence[pt1]; // 다음 순서를 위해 pt1 인덱스 값 지우고
            // pt1을 증가 시킴. 단, pt1과 pt2가 동일하다고 하면 pt2도 증가시켜야함.
            // pt1만 증가 되면 다음 차순에서는 sum이 k보다 작기에 pt2가 증가 되고 pt2의 인덱스값을 sum에 더해줄 것이다.
            if (pt1 == pt2) pt2++; 
            if (pt2 == sequence.size())break;
            pt1++; 
        }
    }
    // q의 첫 인덱스가 다중조건을 만족하는 첫번째 인덱스로 answer에 px1, px2 넣음.
    answer.push_back(q.top().px1);
    answer.push_back(q.top().px2);
    
    return answer;
}

 

 

회고: 투포인터 알고리즘 바로 알았지만 구현에 시행착오가 있었다.