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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

코드설명

포인터 2개가 처음부터 같은방향으로 진행해나가는 투포인터를 활용하는 문제입니다.

 

투포인터를 활용하여 시간복잡도가 O(2*N) 입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = 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());
    	}
    	
    	twoPointer();
    	System.out.println(answer);
    }
    
    public static void twoPointer() {
    	int start = 0;
    	int end = 0;
    	int intervalSum = 0;
    	
    	while(start < N) {
    		
    		while(intervalSum < M && end < N) {
    			intervalSum += arr[end];
    			end += 1;
    		}
    		
    		if(intervalSum == M) {
//    			System.out.println(" "+start+" "+end);
    			answer += 1;
    		}
    		
    		intervalSum -= arr[start];
    		start += 1;
    	}
    	
    }
 
    
}

'알고리즘 > Two Pointer' 카테고리의 다른 글

[백준] 2531 회전 초밥 - 슬라이딩 윈도우(Sliding Window) + 투포인터(Two Pointer) + 원형(Circular) + HashMap(해시맵) JAVA  (0) 2023.08.09
[백준] 20922 겹치는 건 싫어 - 투 포인터 + HashMap JAVA  (0) 2023.08.09
[백준] 1940 주몽 - 투 포인터 + 정렬 JAVA  (0) 2023.08.03
[백준] 2018 수들의 합 5 - 투 포인터 JAVA  (0) 2023.08.02
[백준] 2470 두 용액 - 투포인터(Two Pointer) JAVA  (0) 2023.07.29

+ Recent posts

티스토리툴바