[240321] 알고리즘 리부트 35일차 - 백준 2003, 1806 자바

[Part1-Chapter08-Clip01]

- 백준 2003 수들의 합2

투 포인터란 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘을 말한다. 포인터를 사용하는 방식은 다음과 같이 다양할 수 있다. 1) 같은 배열에서 동일한 방향으로 이동하는 투포인터 (이 경우 2003 문제이다.)  2) 같은 배열에서 마주보는 방향으로 이동하는 투포인터 3) 서로 다른 배열에서 이동하는 투포인터. 이때 두 포인터 중 경우에 따라 하나 또는 모두가 끝에 도달할 때까지 반복한다. 

아래는 부분합 배열을 구현하여 풀이한 것이다. l과 r을 시작 원소와 끝 원소의 인덱스로 지정하고 해당 구간의 부분합이 m과 비교하여 큰지 작은지 같은지에 따라 포인터를 움직임으로써 경우의 수를 셀 수 있게 구현하였다.

package BaekJoon.twopointer;


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

public class BJ2003 {
    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 m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n + 1];
        int[] acc = new int[n + 1];

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //System.out.println(Arrays.toString(arr));

        acc[1] = arr[1];
        for (int i = 2; i <= n; i++) {
            acc[i] = acc[i - 1] + arr[i];
        }
        //System.out.println(Arrays.toString(acc));

        int cnt = 0;

        int l = 1;
        int r = 1;

        while (l <= n && r <= n) {
            //System.out.printf("l은 %d, r은 %d", l, r);
            //System.out.println();
            if (acc[r] - acc[l - 1] == m) {
                r++;
                cnt++;
                //System.out.println("더해졌어요");
            } else if (acc[r] - acc[l - 1] > m) l++; // 구간을 좁혀야 합이 줄어들기 때문
            else r++;
        }

        System.out.println(cnt);


    }
}

아래 코드는 강의에서 다룬 코드이다. 부분합을 구하지 않더라도 투포인터만으로 문제를 풀 수 있다. i를 기준으로 오른쪽 인덱스 변수를 별도로 두고 탐색을 시작한다. i는 시작지점이고 r을 움직여가면서 만약 m보다 크거나 같다면 반복문을 빠져나온다. 만약 m보다 큰 경우 현재 시작점에서부터 오른쪽 인덱스의 원소까지 더하면 m과 일치하는 합을 구할 수 없기 때문에  그 때는 시작점의 원소 값을 합에서 빼고 시작점을 움직여서 판별을 다시 시작한다. 

package BaekJoon.twopointer;

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

public class BJ2003_1 {
    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 m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n + 1];

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //System.out.println(Arrays.toString(arr));


        int cnt = 0;

        int rightIdx = 1;

        int currentSum = arr[1];

        // 여기서는 시간 복잡도가 n^2이 아니다. 전체 배열을 보는 게 아니라 경계값만 보고 있음 O(n)임

        for (int i = 1; i <= n; i++) {
            while (currentSum < m && rightIdx < n) {
                currentSum += arr[++rightIdx];
            }
            if (currentSum == m) cnt++;
            // 만약 현재까지 더한 값이 m과 같은 게 아니라 컸다면 이 시작점에서는 m을 만들 구간이 없다는 것을 의미하니까
            // 시작점의 값을 뺀 기존의 합인 값이 m과 비교해서 작은지 큰지 또 비교한다.
            currentSum -= arr[i];
        }
        System.out.println(cnt);
    }

}

[Part1-Chapter08-Clip02]

- 백준 1806 부분합

수들의 합 2 문제와 비슷한데 같을 때 뿐만 아니라 초과하는 경우도 찾아야 하고 구간의 길이가 가장 짧은 경우를 그 때 그 때 기록해뒀다가 최솟값으로 갱신해가며 반환하는 문제이다.

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

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 s = 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 minLen = Integer.MAX_VALUE;

        int rightIdx = 0;
        int tmpSum = arr[0];
        for (int i = 0; i < n; i++) {
            //System.out.println("현재 i: " + i);

            while (tmpSum < s && rightIdx < n - 1) {
                tmpSum += arr[++rightIdx];
                //System.out.println("현재 tmpSum: " + tmpSum);
            }

            if (tmpSum >= s) {
                minLen = Math.min(minLen, rightIdx - i + 1);
                //System.out.println("현재 minLen: " + minLen);
            }

            tmpSum -= arr[i];
            //System.out.println("현재 값 뺐어요");
        }

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

    }
}