투 포인터 알고리즘에 대한 설명 + 백준 - 수들의 합2_2003번 문제 풀이

투 포인터 개념

각 원소마다 모든 값을 순회해야할 때,
*연속하다는 특성을 이용해서 처리,

 

단순 반복문을 이용해서 문제를 해결하려고 하면, 시간 복잡도가 O(N^2), O(N^3)인 경우가 있기 때문에 투 포인터 알고리즘을 이용해서 문제를 해결해야 된다.

 

포인터 2개가 1차원 배열을 증가하는 방향으로만 순회하므로 O(N) + O(N) = O(N)

이 알고리즘을 처음 접했을 때 어려웠는데 이제는 기본적인 문제는 풀 수 있게 되었다. 그만큼 계속 반복함!

 

https://www.acmicpc.net/problem/2003 이 문제를 기반으로 설명을 하겠따.

 

n개로 나열 된 수, +해서 m이되는 경우의 수를 구하자

 

- 자연수로 이루어진 1차원 배열이 주어진다.

- 연속되는 부분 배열 중 원소의 합이 M이 되는 경우의 수를 구하는 문제

 

= 접근 방법 =

1. 초기 포인터를 2개 설정 => 0으로 초기화.

2. start ~ end에 포함되는 구간은 현재 부분 배열이다.

3. start는 항상 end보다 작거나 같아야 함.

4. 포인터는 항상 증가한다.

 

= 포인터가 움직일 때 =

1. 현재 부분 배열의 합이 M보다 작을 때, => end++

2. 현재 부분 배열의 합이 M보다 클 때,     => start++

3. 현재 부분 배열의 합이 M과 같을 때, => end++  

 

= 문제 + 그림을 통한 자세한 설명 =

 

 

이런식으로 하나하나씩 찾는 과정이라고 생각하면 된다.

 

 

정답은 3

N = 10, M = 5, => 10개 나열 된 수를 이용해서 합했을 때 5가 되는 경우의 수를 구하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 1. input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        } // 여기까지, 입력

        int start = 0; // 왼쪽 index
        int end = 0; // 오른쪽 index
        int count = 0; // K = 5일 때, count를 1개씩 증가
        int sum = 0;
        while (start < n && end < n) {
            sum = 0;
            for (int i = start; i <= end; i++) {
                sum += arr[i];
            }

            if (sum < k) {
                end++;
            } else if (sum > k) {
                start++;
            } else if (sum == k) {
                count++;
                end++;
            }
        } 

        System.out.println(count);
    }
}

 

간단하게 구현 끝!