[알고리즘] 투포인터 알고리즘 Two Pointers Algorithm

💡 개념

    일차원 배열에서 두 개의 포인터를 이용해 원하는 값을 찾는 알고리즘. 이중 for문을 사용하는 경우의 시간 초과를 피할 수 있다.

① 만약 현재 부분합이 목표값S 이상이거나, 이미 high = 배열크기N이면 low++
② 그렇지 않다면 high++
③ 현재 부분합이 S과 같으면 결과++

...

💡 관련 문제: 프로그래머스

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector <int> arr;
    int answer = 0;
    int ptr1 = 1;
    int ptr2 = 1;
    int sum = 1;
    
    arr.push_back(0);
    for(int i=1;i<=n;i++) {
        arr.push_back(i);
    }
    
    while(ptr2<=arr.size()) {
        if(sum==n) {
            answer++;
            sum-=ptr1;
            ptr1++;
        } else if(sum<n) {
            ptr2++;
            sum+=ptr2;
        } else {
            sum-=ptr1;
            ptr1++;
        }        
    }
      
    return answer;
}

참고링크