[백준 2003] - 수들의 합2

JIWOO YUN·2023년 4월 11일
0
post-custom-banner

문제링크

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

구현방법

만약 2중for문을 통해서 체크를 진행한다면 이 문제의 경우 최대 N이 10000이기때문에 1억ms가 걸린다. -> 이경우 시간초과가 발생가능하다. 그렇기 때문에 투포인터 알고리즘을 통해서 진행하였습니다.

투포인터 알고리즘의 경우 O(N) 의 시간복잡도를 가지기 때문에 시간초과를 피할 수있습니다.

구현알고리즘

투 포인터 알고리즘

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        int result = 0;

        //M값 체크용
        int check_sum = 0;
        int start_idx = 0;
        int end_idx = 0;
        while (start_idx != N) {
            if(end_idx == N){
                check_sum -= list[start_idx++];
                if(check_sum == M)
                    result+=1;
                continue;
            }


            if(check_sum >= M){
                check_sum -= list[start_idx++];
            }
            else if(check_sum < M){
                check_sum += list[end_idx++];
            }

            if(check_sum == M){
                result+=1;
            }
        }

        System.out.println(result);
    }
}
profile
열심히하자
post-custom-banner

0개의 댓글