[프로그래머스] 연속된 부분 수열의 합(Java), 투포인터

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

프로그래머스

---

문제 풀이

while문을 사용해

1) sum(누적 합)이 k보다 작다면 right를 증가시키며 더해주고

2) k보다 작거나 right가 sequence의 끝까지 도달했다면 left를 증가시키며 빼준다.

3) sum이 k와 같은 경우 이를 list에 담아 저장해둔다.

 

-> list를 정렬 시킨 후 제일 앞에 있는 값을 반환해준다.

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        List<int[]> list = new ArrayList<>();
        
        int left = 0; 
        int right = 0;
        int sum = 0;
        
        while(left < sequence.length) {
            if(sum > k || right == sequence.length) {
                sum -= sequence[left];
                left++;
            } else {
                sum += sequence[right];
                right++;
            }
            
            if(sum == k) {
                list.add(new int[]{left, right - 1});
            }
        }
        
        list.sort((o1, o2) -> {
            // 간격이 짧은 순으로 정렬
            // 간격이 같다면 더 앞에 있는 순서대로 정렬
            int size1 = o1[1] - o1[0]; 
            int size2 = o2[1] - o2[0];
            if(size1 == size2) {
                return o1[0] - o2[0];
            } else {
                return size1 - size2;
            }
        });
        
        answer = list.get(0);
        return answer;
    }
}

---

투포인터 알고리즘이란?

- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

- 일반적으로 왼쪽 포인터와 오른쪽 포인터를 사용하며, 각각 탐색 범위의 시작과 끝을 가리킨다.

- 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이나 합을 계산하는데 주로 사용한다.

 

투포인터 수행 단계

1. 배열 또는 리스트의 시작 위치에 두 포인터를 설정한다.

2. 두 포인터 사이의 구간을 조사하고 조건을 확인한다.

3. 조건을 만족시킬 경우 알고리즘을 종료하고, 만족하지 않을 경우 첫번째 또는 두번째 포인터를 이동시킨다.

4. 2번으로 돌아가 반복한다.

 

투포인터 시간 복잡도 : O(n)

투포인터 알고리즘은 선형시간 복잡도를 가진다.

한 번의 반복으로 모든 요소를 처리하기에 효율적이다.