[코드트리 챌린지] 세 수의 최대 곱(S3)

 

문제 : 가장 짧은 부분합

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제는 아래와 같다

원소가 n개 들어 있는 수열에서 특정 구간을 잡았을 때

그 합이 s 이상이 되는 것 중, 가장 짧은 구간의 길이를 구하는 프로그램을 작성해보세요.

 

첫 번째 줄에 n과 s가 공백을 두고 주어집니다.

두 번째 줄에 수열의 각 원소가 공백을 두고 차례대로 주어집니다.

• 1 ≤ n ≤ 100,000
• 1 ≤ s ≤ 109
• 1 ≤ 원소 값 ≤ 10,000

 

실력 진단에서 틀린 문제이고 처음 투 포인터를 생각하긴 했지만,

원소 값이 10,000이길래 n^2으로도 풀리리라 생각돼 2중 for문을 작성해서 풀었다.

이후 시간 초과가 났고 문제를 자세히 읽어보니 원소 각각의 값이 10,000이고 이를 n으로 착각했지만,

실제 시간복잡도에 영향을 주는 n은 100,000으로 제곱하면 10억이 나오므로 틀린 풀이였다.

 

그래서 따로 다시 풀어볼 겸 투 포인터 개념을 점검해보았고, 아래와 같은 풀이로 풀었다.

0. 모든 구간은 left와 right 사이를 의미

1. 처음 left와 right은 0에서 시작

2. 문제 조건상 구간의 합이 s 이상이 되는 가장 짧은 구간을 구하므로, 구간의 합이 s 미만인 경우 계속 구간을 키움

3. 구간의 합이 s 이상이 되는 처음 시점에 그 구간과 최소 구간을 비교해 작은 값을 대입 

4. 이후 left값을 한 칸 앞으로 옮겨주며 옮기기 전에 구간에서 left 위치에 있는 값을 빼줌

 

시간복잡도를 계산하면

1. 1~4번 풀이는 최대 O(2N)이다.

 

코드는 아래와 같다

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;

    static int n, s;
    static int[] inputArr;
    static void input() throws IOException{

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

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

    static void pro(){

        int minDiff = Integer.MAX_VALUE;
        int right = 0;
        int sum = 0;
        for (int left = 0; left < n; left++) {
            while (right < n) {
                if (sum >= s) {
                    minDiff = Math.min(right - left, minDiff);
                    break;
                }
                sum += inputArr[right++];
            }
            sum -= inputArr[left];
        }
        if (minDiff == Integer.MAX_VALUE) minDiff = -1;
        System.out.println(minDiff);
    }


    public static void main(String[] args) throws IOException{
        input();
        pro();
    }

}