Java 백준 문제풀이 (40) 2018번: 수들의 합5

 

투포인터 알고리즘의 시간복잡도는 기본적으로 O(N)이지만 배열이 정렬된 상태에서만 사용할 수 있기 때문에 정렬이 필요할 경우 일반적으로 많이 쓰이는 병합 정렬, 퀵 정렬을 생각했을 때 O(nlogn)이 될 수 있다.

(물론 원본 배열 형태와 정렬 방법에 따라 이는 달라진다.)

 

 

 

 

 

투 포인터 알고리즘은 기본적으로는 이런 형태다.

문제에 따라 포인터 위치나 움직이는 방법은 달라진다.

 

실전 예제로 살펴보자.

 

 

 

 

 

어떤 자연수 1 <= N <= 10,000,000에 대해 N이하 자연수의 연속된 합으로 이를 구하는 문제다.

투 포인터를 활용하면 반복문으로 최대 N번 안에 정답을 구할 수 있으므로 시간 복잡도는 O(N)이 된다.

 

나처럼 지능이 특별할 것 없는 평범한 인간이고, 어떤 문제유형 처음 접한다면 해설을 보지 않고 답을 구할 수 있는 가장 빠른 방법은 직접 그려보는 것이다.

 

위 예제에서 입력값은 15 출력값은 4가 나왔다.

N이하의 자연수만 허용하기 때문에 (당연하지만) 1부터 15까지만 더할 수 있다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

 

가장 처음 15가 나오는 시점은 언제일까?

포인터를 1번 포인터, 2번 포인터로 분류했을 때 2번 포인터가 5번까지 위치하는 동안 ~ 1번 포인터부터 2번 포인터까지의 값을 모두 더한다는 코드를 작성한다면?

 

1+2+3+4+5로 15가 나온다.

그리고 여기서 2번 포인터가 한 번 더 움직이면 21이 되어버리는데, 이 상태에서 2번 포인터를 움직여봤자 15와 점점 멀어질 뿐이다.

어떻게 해야할까?

 

이제 1번 포인터를 움직이며 1번 포인터가 위치하던 자리의 숫자를 제거하면 된다.

 

만약 1번 포인터와 2번 포인터의 합이 우리가 구하려는 숫자 N보다 크다면 1번 포인터를 움직이고, N보다 작다면 2번 포인터를 움직이는 식으로 값을 계속 조정하면 된다.

 

예를들어 2번 포인터가 6에 위치할 때 값은 21이므로 15보다 작거나 같은 수가 될 때까지 1번 포인터를 움직인다.

결국, 1번 포인터가 4번까지 이동하면 1,2,3을 버리고 4,5,6만 남아 다시 15가 완성될 것이다.

이걸 1번 포인터와 2번 포인터가 겹치는 순간까지 반복하면 모든 경우의 수를 구할 수 있다.

 

사실 이렇게 장황하게 설명하기엔 너무 쉬운 문제인데 쓰다보니 또 투머치토커가 되어버렸다..

 

정답은 밑에 있다. 늘 그렇듯 남의 코드를 보고 답을 적어봤자 다음 주면 잊어버린다.

스스로 풀면 2주 뒤에 잊어버림 ㅋㅋ후..

 

 

 

 

 

 

 

 

 

 

 

import java.io.*;
import java.util.*;
 
public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        int start_pointer = 0;
        int end_pointer = 0;
        int sum = 0;
        int count = 0;
 
        while ( start_pointer <= N ) {
 
            if ( sum == N ) {
                count++;
                sum += end_pointer;
                end_pointer++;
            }
 
            if ( sum < N ) {
                sum += end_pointer;
                end_pointer++;
            }
 
            if ( sum > N ) {
                sum -= start_pointer;
                start_pointer++;
            }
        }
 
        System.out.println(count);
    }
}