[Java] 백준 2003 수들의 합 2

2003 수들의 합 2 문제 링크

문제분석

• N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성

제약 사항

• A[x]는 30,000을 넘지 않는 자연수

입력 조건

• 첫째 줄 : N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)
• 둘째 줄 : A[1], A[2], …, A[N]이 공백으로 분리되어 주어짐

출력 조건

• 경우의 수를 출력

#1

import java.awt.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

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

        int start = 0;
        int answer = 0;

        while (start<N) {
            int sum = 0;
            for (int i=start; i<N; i++) {
                sum+=arr[i];
                if(sum==target) {
                    answer++;
                    continue;
                } else if (sum>target) continue;
            }
            start++;
        }
        bw.write(answer+"");

        bw.flush();
        bw.close();
    }
}

• 맞았음
• 근데 포인터를 하나만 사용했고, 시간복잡도가 O(N)이 나왔는데 이게 투 포인터가 맞나..?

#2

• 조건문을 조정해서 시간복잡도 O(N)으로 만듦
• 포인터 두개 사용함
• 투 포인터 같다 🤭🤭

import java.awt.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

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

        int start = 0;
        int end = 0;
        int answer = 0;
        int sum = 0;

        while (start<N && end<N) {
            sum+=arr[end];

            if(sum==target) {
                sum = 0;
                answer++;
                start++;
                end = start;
            } else if (sum<target) {
                end++;
            } else {
                sum=0;
                start++;
                end = start;
            }
        }
        bw.write(answer+"");

        bw.flush();
        bw.close();
    }
}

• 성공!!!