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

 

다시 푸는 문제 !

마찬가지로 투포인터를 이용해 풀이할 수 있었다.

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

using namespace std;

int cmp(pair<int, int> a, pair<int, int> b) {
    int aLen = a.second - a.first;
    int bLen = b.second - b.first;
    if(bLen == aLen)
        return a.first < b.first;
    else
        return aLen < bLen;
}


vector<int> solution(vector<int> sequence, int k) {
    vector<pair<int, int>> answer;
    int result = 0;
    int j = 0;
    for(int i = 0; i < sequence.size(); i++) {
        while(result < k && j < sequence.size()) {
            result += sequence[j];
            j++;
        }
        if(result == k) {
            answer.push_back({i, j - 1});
        }
        result -= sequence[i];
    }
    sort(answer.begin(), answer.end(), cmp);

    return {answer[0].first, answer[0].second};
}

 

 

---

 

다시 풀었다.

투포인터는 풀 때마다 어렵다 ㅎㅎ

투포인터는 두 가지 접근 방법이 있는데

 

1. 오른쪽이 될떄까지 가보고 왼쪽이 하나씩 당겨지는 방식

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

using namespace std;

// 길이, 시작인덱스, 마지막인덱스로 정렬

struct PQ {
    int len;
    int start;
    int end;
    
    bool operator<(const PQ& other) const {
        if(len != other.len) return len > other.len;
        if(start != other.start) return start > other.start;
        if(end != other.end) return end > other.end;
    }
};

priority_queue<PQ, vector<PQ>> pq;


vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int j = -1;
    int totalValue = 0;
    
    for(int i = 0; i < sequence.size(); i++) {
        
        while(totalValue < k && j + 1 < sequence.size()) {
            totalValue += sequence[++j];
        }
        if(totalValue == k) {
            pq.push({j - i, i, j});
        }
        totalValue -= sequence[i];
    }
    
    return {pq.top().start, pq.top().end};
}

 

2. 오른쪽이 하나씩 가지고 왼쪽이 될떄까지 당겨지는 방식

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

using namespace std;

// 길이, 시작인덱스, 마지막인덱스로 정렬

struct PQ {
    int len;
    int start;
    int end;
    
    bool operator<(const PQ& other) const {
        if(len != other.len) return len > other.len;
        if(start != other.start) return start > other.start;
        if(end != other.end) return end > other.end;
    }
};

priority_queue<PQ, vector<PQ>> pq;


vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    
    int start = 0;
    int totalValue = 0;
    
    for(int end = 0; end < sequence.size(); end++) {
        
        totalValue += sequence[end];
        
        while(totalValue > k && start < sequence.size()) {
            totalValue -= sequence[start++];
        }
        
        if(totalValue == k) {
            pq.push({end - start, start, end});
        }
        
    }
    
    return {pq.top().start, pq.top().end};
}

 

 

이렇게 두 가지 방법이 있다. 후자가 더 쉬운듯??