[실버 4] 수들의 합 2

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

2003번: 수들의 합 2

개절은 문제

 

정렬해서 index=  0 , N-1에 투 포인터로 풀면 되지 않을까? 해서 코드를 다 짰는데

방금 말한 것은 숫자를 2개 뽑아서 M과 일치하는지 검사하는 문제이고

이 문제는 연속된 배열의 숫자 X 개를 뽑아 합이 M과 같은지 검사하는 문제이다

 

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

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

int answer = 0;

int index1 = -1;
int index2 = -1;

int sum = 0;

while (index2 < N - 1) {
    if (sum > M) {
        sum -= number[++index1];
    } else if (sum == M) {
        answer++;
        sum -= number[++index1];
        sum += number[++index2];
    } else {
        sum += number[++index2];
    }
}

while (index1 < N - 1) {
            if (sum == M)
                answer++;
            sum -= number[++index1];
        }

        sb.append(answer);
        System.out.println(sb);
    }
}

index2는 이미 N-1에 도달

index1은 자기 뒤에부터 sum에 더하는 것이므로 N-1에 도착하면 모두 순회한 것

 

index1만 당기면서 sum -= 해주기

 

O(N)

 

public static void twoPointer() {
    int sum = 0;
    int end = 0;
    for (int start = 0; start < N; start++) {
        while( sum < M && end< N)
            sum += A[end++];
        
        if(sum == M)
            cnt++;
        
        sum-= A[start];
    }
}

다른 사람의 풀이 제일 직관적임