(Java) 투포인터 (feat. 백준 1806 부분합)

투포인터

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색하는 알고리즘이다.

2개의 숫자를 합했을 때 40에 가장 가까운 수 찾기

 

 

위의 예시처럼 2개의 포인터를 옮김으로써 이루어진다.

완전탐색에 비해 시간복잡도를 많이 아낄 수 있다.

while (start < end) {
    int sum = nums[start] + nums[end];
    if (sum == target) {
        return true; // pair exists
    } else if (sum < target) {
        start++; // move start forward to get larger value
    } else {
        end--; // move end backward to get smaller value
    }
}

 

코드 예시이다. while문 내에 탈출 조건문과 포인터를 옮겨주는 조건, 얼마나 옮길건지를 작성해주면 완성이다.

어찌보면 for문에서 인덱스 초기 조건, 반복문 탈출 조건, 인덱스 이동을 작성하는 것과 같이 이루어지는데 다른 부분이라면 문법이 아닌 내가 직접 구현한다는데 차이점이 있는 것 같다.

 

 

 

백준 1806 부분합

길이가 N인 수열이 주어지고 합이 S 이상인 부분합들 중 최단 길이를 구하라는 문제였다.

문제를 읽었을 때 부분합이라는 단어와 길이가 한번에 와닿지 않아 헷갈렸던 문제이다.

부분합이란, 급수에서 첫째항부터 n 항까지의 합을 의미한다. 즉, 연속된 수들의 합이다.

그리고 길이는 연속된 수열의 길이를 의미한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int NArr[] = new int[N+1];
        int S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            NArr[i] = Integer.parseInt(st.nextToken());
        }

        int min = Integer.MAX_VALUE;
        int start = 1;
        int end = 1;
        int sum = NArr[1];
        while(end <= N) {
            if(sum >= S) {
                int len = end - start + 1;
                min = Math.min(len, min);
                if(start + 1 > N) break;
                sum -= NArr[start++];
                if(sum == 0) {
                    if(end + 1 > N) break;
                    sum += NArr[++end];
                }
            } else {
                if(end + 1 > N) break;
                sum += NArr[++end];
            }
        }

        min = min == Integer.MAX_VALUE ? 0 : min;
        System.out.println(min);
    }
}

 

 

버그 디버그

1. 포인터를 옮겨주는 시점과 배열 범위 내인지 확인하는 패딩 조건을 실행하는 시점, 포인터에 따라 배열을 탐색하는 시점이 뒤섞여 NullPointerError가 많이 일어났다. 별도로 메소드로 분리해 알고리즘을 부분부분 디버깅했다면 구조를 더 쉽게 파악할 수 있었을 것 같다.

2. 문제 조건 중에 하나인 합을 만드는 것이 불가능하다면 0을 출력한다를 빼먹고 있었다. 풀기 전에 조건들을 정리해두는 습관을 들이면 좋을 것 같다.

 

 

느낀점

투포인터는 while문 내에 내가 직접 조건들을 달아줘야 하므로 실수할만한 부분이 많은 알고리즘이다. 조건이 세부적일수록 어려우니 주의를 하고 풀어야 할 것 같다.