코드트리 조별과제 4회차 (8.05 ~ 8.11)

Two Pointer

 

[ 문제 ]

[4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 특정 구간을 선택하여 구간 내 숫자의 합이 10이 넘지 않으면서 가장 큰 구간의 크기를 구하는 프로그램을 작성하시오.

 

 

[ 해결책(1) - O(N^2) ]

무작정 코드를 작성한다면, 아래 코드처럼 모든 구간 O(N^2)개를 잡아보면서 합이 10을 넘지 않는 경우 중 구간 크기의 최댓값을 구한다.

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
        int k = 10;
        int n = 6;
 
        // 가능한 구간 중 최대 크기를 구합니다.
        int ans = 0;
 
        // 모든 구간을 탐색합니다.
        for(int i = 1; i <= n; i++) {
            // 구간 내 합이 10을 넘지 않을때까지 계속 진행합니다.
            int sumVal = 0;
            for(int j = i; j <= n; j++) {
                sumVal += arr[j];
 
                // 구간 내 합이 10을 넘게되면 그만 진행합니다.
                if(sumVal > k)
                    break;
 
                // 현재 구간 [i, j]는 
                // 유효한 구간이므로
                // 구간 크기 중 최댓값을 갱신합니다.
                ans = Math.max(ans, j - i + 1);
            }
        }
 
        // 조건을 만족하는 가장 큰 구간의 크기는
        // [4, 2, 1]로 3이 됩니다.
        System.out.print(ans);
    }
}
 

 

 

[ 해결책(2) - O(N) ]

O(N^2)의 풀이법에서 알 수 있듯이 i가 1씩 증가할 때마다, 최대로 뻗어나갈 수 있는 j의 위치는 항상 같거나 증가한다는 것을 확인할 수 있다. 그 이유는 i가 1이 증가하면 Arr[i]만큼 감소하기 때문에 그만큼 뒤로 이동할 수 있는 여유 공간이 존재하기 때문이다.

이렇듯 문제에서의 특정 조건에 의해 원하는 구간의 양 끝을 나타내는 2개의 포인터가 한 방향으로만 계속 전진하는 형태의 테크닉을 Two Pointer라고 부른다.

Two Pointer를 이용해 i가 1 증가했을 때 j는 이전 값에서 시작하여 감소시키지 않고 최대로 뻗어 나가도록 하면 i, j 모두 한 방향으로만 진행하기 때문에 O(N)이 된다. 아래의 코드를 통해 이해하자.

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
        int k = 10;
        int n = 6;
 
        // 가능한 구간 중 최대 크기를 구합니다.
        int ans = 0;
 
        // 구간을 잡아봅니다.
        int sumVal = 0;
        int j = 0;
        for(int i = 1; i <= n; i++) {
            // 구간 내 합이 10을 넘지 않을때까지 계속 진행합니다.
            while(j + 1 <= n && sumVal + arr[j + 1] <= k) {
                sumVal += arr[j + 1];
                j++;
            }
 
            // 현재 구간 [i, j]는
            // i를 시작점으로 하는
            // 가장 긴 구간이므로
            // 구간 크기 중 최댓값을 갱신합니다.
            ans = Math.max(ans, j - i + 1);
 
            // 다음 구간으로 넘어가기 전에
            // arr[i]에 해당하는 값은 구간에서 제외시킵니다.
            sumVal -= arr[i];
        }
 
        // 조건을 만족하는 가장 큰 구간의 크기는
        // [4, 2, 1]로 3이 됩니다.
        System.out.print(ans);
    }
}
 

실제로 2중 포문으로 작성되어 있지만, ( i, j )는 모두 한 방향으로만 진행하기 때문에 시간복잡도가 이중 포문이 아닌 합으로 나타내짐에 유의하자.

 

연습문제 - (코드트리) 가장 짧은 부분

 

https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, S, Arr[], ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
 
        Arr = new int[N+1];
 
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            Arr[i] = Integer.parseInt(st.nextToken());
        }
 
        ans = Integer.MAX_VALUE;
 
        solve();
 
        if(ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }
 
    static void solve(){
        long sum = 0;
        int j = 0;
 
        for(int i=1; i<=N; i++){
 
            while(j+1<=N && sum<S){
                sum += Arr[j+1];
                j++;
            }
 
            if(sum<S) break;
 
            ans = Math.min(ans, j-i+1);
 
            sum -= Arr[i];
        }
    }
}