투포인터 알고리즘

투 포인터 알고리즘

: 정렬된 1차원 배열 내에서 시작과 끝을 가리키는 2개의 포인터를 설정한 후 이를 조작해가며 원하는 것을 얻는 알고리즘이다.

 

사용

- 배열 또는 리스트에서 특정 조건을 만족하는 부분 배열 또는 부분 리스트 찾기

- 배열에서 합이 특정 값이 되는 두 요소 찾기

- 정렬된 배열에서 특정 합이 되는 요소 쌍 찾기

 

시간 복잡도

: O(n)

- 각 포인터가 n번 누적 증가해야 알고리즘이 끝나기 때문에 O(n) 시간복잡도가 발생한다.

 

필요성

: 완전 탐색의 경우 O(n²) 시간복잡도가 발생하지만 투 포인터 알고리즘을 사용하면 O(n)의 시간복잡도가 발생한다.

 

공식

ex) 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력

- 모든 경우를 확인할 때까지 반복

     - 합 < 특정 값: end 포인터 이동하고 해당 값을 합에 더함

     - 합 > 특정 값: 합에서 start 포인터가 가리키는 인덱스의 값을 뺀 후 start 포인터 이동

     - 합 == 특정 값: count 변수를 1 증가시키고 합에서 start 포인터가 가리키는 인덱스의 값을 뺀 후 start 포인터 이동

- count 출력

import java.io.*;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());
        long n = Long.parseLong(input.nextToken());
        long start = 1;
        long end = 2;
    	long sum = start + end;
    	long count = 1;
    	
    	sum = start;
    	while(start < n && end <= n) {
    		if(sum < n)
    			sum += end++;
    		else if(sum > n){
    			sum -= start;
    			start++;
    		}
    		else {
    			count++;
    			sum -= start;
    			start++;
    		}
    	}
    	System.out.println(count);
    }
}

 

그림 설명