[java 백준] 골드 4/ 1806번 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static long s;
    public static int[] arr;
    public static int cnt = 0;
    public static int ans = 100001;
    public static int sum = 0;
    public static int left, right = 0;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        while (true) {
            if (sum >= s) {
                sum -= arr[left++];
                ans = Math.min(right - left + 1, ans);
            } else if (right == n) {
                break;
            } else {
                sum += arr[right++];
            }
 
        }
 
        if (ans == 100001) {// 합을 만들지 못해서 원래 ans값 그대로 나옴
            System.out.println(0);
        } else {
            System.out.println(ans);
        }
 
    }
 
}

 

 

이 문제는 어쩔 수 없이 완전탐색 카테고리에 넣었는데 절대절대 완전탐색으로 풀면 안된다.

나는 투포인터를 완전탐색으로 잘못 이해해서 이거 때문에 시간초과가 자꾸 떴다. 

 

내가 잘못이해했던 부분은 

i는 그대로 있고 j가 계속 탐색을 하는데 i부터 j까지 합(cnt)이 s가 되면 i와 j사이의 거리를 저장하고 i를 1만큼 증가시켰다. 또는 합이 s가 되지 않더라고 j의 범위가 n-1보다 커지면 i를 1 증가시킨다음에  while문을 중단시켰다. 

그리고 다시 재귀를 통해 함수에 들어오면 i와 j의 위치를 같게 해줬다. 

이렇게 되면 i와 j가 같이 움직이지 않기에 j가 완전탐색을 하는 완전 비효율적인 상황이 생겨난다.

 

틀린코드​

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static long s;
    public static int[] arr;
    public static int cnt = 0;
    public static int ans = 100001;
    public static int sum = 0;
    public static int left, right = 0;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        while (true) {
            if (sum >= s) {
                sum -= arr[left++];
                ans = Math.min(right - left + 1, ans);
            } else if (right == n) {
                break;
            } else {
                sum += arr[right++];
            }
 
        }
 
        if (ans == 100001) {// 합을 만들지 못해서 원래 ans값 그대로 나옴
            System.out.println(0);
        } else {
            System.out.println(ans);
        }
 
    }
 
}

 

 

 

하지만 투포인터를 사용해서 풀면  우선 i와 j가 똑같은 위치에서 시작한다.

cnt값이 s보다 작으면 right인덱스를 1만큼 더해서 그 원소를 cnt에 더해준다.

cnt값이 s보다 크거나 같으면  left인덱스를 1만큼 더해서 cnt에 그 원소를 빼준다.

이러면 굳이 한쪽이 완전탐색을 하면서 한번 방문했던 노드를 또 방문하는 그런 비효율적인 짓을 하지 않아도 된다.

만약 right가 n이면 break를 걸어준다. (n-1일때 즉, 마지막 인덱스의 원소가 s일수도 있기 때문!)

 

이러면 인덱스가 완전탐색하는 일도 없고 재귀도 없기에 시간초과가 일어나지 않는다. (재귀함수도 시간복잡도가 O(n)이나 되었다..허허허)

 

진짜 어이없는거에서 계속 틀렸습니다가 나왔는데 이유는

1) 만약에 합이 s가 되지 못하는 경우에 0을 출력해야했다. 그래서 if문을 if(ans==1000001)으로 했어야 했는데 (합이 s가 되지 못하면 ans 값은 변하지 않을 것이고 ans는 그대로 1000001 유지했을 것)

if(ans==0)으로 해버렸다 ㅋㅋ 띠용 ㅋㅋㅋ

2) 또 문제를 잘못 읽었는데 나는 s이상이 아니라 합이 s가 될때라고만 봤다. 어쩐지 너무 어렵게 생각했다..ㅜ

 

 

참고자료

https://settembre.tistory.com/350

[백준/자바] 1806 부분합