[Java] 백준 수들의 합 2

1. 문제 분석

연속되는 수들의 합을 구하는 것이고 단순히 for문을 사용한다면 시간 초과가 나올 것이다.

이때 사용하는 것이 투포인터다. 2개의 start와 end를 통해 각 부분의 합을 구하는 것이다.

로직은 생각보다 간단하다. 만약 현재 합이 목표값 보다 작다면 end를 증가, 크거나 같다면 start를 증가를 하면 된다.

말로하는 것 보다 직접 하나씩 해보자.

 

테스트 케이스 1을 보자.

1 1 1 1이고 합이 2인 것을 찾아야 한다.

초기 상태다. 합인 sum이 목표값보다 작으니 end를 추가해야한다.

end를 추가한 상태다. 이제 arr[start] + arr[end]는 2가 된다. 목표값이 되었으니 start를 더해주고

sum에서 arr[start]를 빼준다(arr[start]는 더해주기 전 상태다.)

다시 합이 1인 상태로 돌아왔다. end를 더해줘야한다.

이처럼 계속 늘어나다가 end가 배열의 크기가 된다면 반복문을 종료하면 된다.

2. 구현

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        int answer = Integer.parseInt(st.nextToken());

        int[] arr = new int[size];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int result = 0;
        int start = 0, end = 0, sum = 0;
    
        //양끝에서 오는 투포인터는 정렬이 필요
        //0부터 시작은 아님!
        while (true) {
            if(sum >= answer){
                if(sum == answer){
                    result++;
                }
                sum -= arr[start++];
            }
            else{
                if(end == size){
                    break;
                }
                sum += arr[end++];
            }
        }
        System.out.println(result);
    }
}

정말 위에서 말한대로 구현하면 끝이다. 딱히 설명할게 없다..

3. 마무리

예전에 풀었던 투포인터를 다시 풀어보니 너무 헷갈렸다.

답지를 보기보단 투포인터의 개념을 다시 잡고 풀어보니 할만했다.