[자료구조]투 포인터

*참고자료

1) Doit 자바 알고리즘 코딩테스트

2) https://butter-shower.tistory.com/226

 

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 데 사용하기 적합하며 리스트에 순차적으로 접근시 두 개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 보통 start_index, end_index 라는 변수를 선언하거나 특정 변수 두 개를 선언하는 방식으로 코드를 구성합니다.

 

문제를 통해 투 포인터 관련 내용 설명해드리겠습니다.

 

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

참고로 이 문제에 주어진 시간 제한은 2초입니다. 그런데 N의 최댓값이 10,000,000으로 매우 크게 잡혀 있습니다. 이런 경우 시간 복잡도가 중요하기 때문에 O(n)의 시간 복잡도 알고리즘을 사용해야 합니다. 이 때 사용하는 방법이 투 포인터입니다. 연속된 자연수의 합을 구해야 하므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하는 방식으로 진행해주시면 됩니다. 

 

*문제풀이

1. 입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 모두 초기화시켜줍니다. 결과 변수를 count 1로 초기화해주는데 N이 15일 때 숫자 15만 뽑는 경우의 수를 미리 고려했기 때문입니다.

 

 

2. 투 포인터 이동 원칙

1) sum(연속된 자연수의 합) > N :

sum = sum - start_index;  start_index++;

 

2) sum(연속된 자연수의 합) < N :

end_index++;  sum = sum + end_index;

 

3) sum(연속된 자연수의 합) == N :

end_index++; sum = sum + end_index; count++;

 

위의 투 포인터 이동원칙을 활용해 배열 끝까지 탐색하면서 합이 N이 되는 경우의 수를 구해줍니다.

start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 동일하며, 

end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장한다는 의미로

생각해주시면 됩니다. sum과 N이 같은 경우에는 경우의 수(count)를 1 증가시키고, end_index를

오른쪽으로 이동시킵니다.

 

3. 2번째 단계를 end_index가 N이 될 때까지 반복해주고, 포인터가 이동할 때마다 현재의 총합과 N을 비교하여 값이 같은 경우 경우의 수(count)를 1만큼 증가시켜주면 끝입니다.

 

○ 원하는 수(15)가 되었을 때 - count 증가, end_index 증가

○ 원하는 수(15)보다 연속된 자연수의 합이 더 큰 경우 1 => start_index 증가

○ 원하는 수(15)보다 연속된 자연수의 합이 더 큰 경우 2 => sum에서 start_index값을 빼준다.

○ 코드 구현

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        int count = 1;
        int start_index = 1;
        int end_index = 1;
        int sum = 1;
 
        // N이 되면 반복문 빠져나옴
        while (end_index != N) {
            if (sum == N) {
                count++;
                end_index++;
                sum = sum + end_index;
            } else if (sum > N) {
                sum = sum - start_index;
                start_index++;
            } else {
                end_index++;
                sum = sum + end_index;
            }
        }
        System.out.println(count);
    }
}