투 포인터

투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

 

문제 풀기

백준 알고리즘 2018번 문제 '연속된 자연수의 합 구하기' 풀이

 

[문제]

자연수 N(1이상 10,000,000이하)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다.

예를 들어 N = 10은 10, 1+2+3+4 2가지로 출력이 2가 나와야 한다.

 

이 문제는 시간 복잡도를 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간은 2초이다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인터이다. 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현하겠다. 시작 인덱스, 종료 인덱스를 투 포인터로 지정한 후 문제에 접근해보자.

 

N변수 저장
사용 변수 초기화(count = 1, start_index = 1, end_index = 1, sum = 1)
while(end_index != N) {
	if(sum == N) count 증가, end_index 증가, sum 값 변경
    else if(sum > N) sum값 변경, start_index 증가
    else if(sum < N) end_index 증가, sum 값 변경
}
count 출력

위 풀이로 소스 코드를 작성해보자.

import java.util.Scanner;

public class App {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 1;
        int start_index = 1;
        int end_index = 1;
        int sum = 1;

        while (end_index != N) {
            if (sum == N) {
                count++;
                end_index++;
                sum += end_index;
            } else if (sum > N) {
                sum -= start_index;
                start_index++;
            } else {
                end_index++;
                sum += end_index;
            }
        }
        System.out.println(count);
    }
}