백준 2003: 수들의 합(java)

문제

---

풀이

---

1. 이중 for문

부분 수열의 왼쪽 인덱스를 i, 오른쪽 인덱스를 j라 한다. i가 n일 때 j를 n, n+1, n+2, ...로 증가시키며 합이 M이 되는 경우를 찾되, sum이 M을 처음으로 초과했을 경우 더 이상 탐색할 필요가 없으므로 반복문을 종료한다.

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());
		
		st=new StringTokenizer(br.readLine());
		int[] num=new int[N];
		for(int i=0; i<N; i++) {
			num[i]=Integer.parseInt(st.nextToken());
		}
		
		int count=0;
		for(int i=0; i<N; i++) {
			int sum=0;
			
			for(int j=i; j<N; j++) {
				sum+=num[j];
				
				if(sum==M) {
					count++;
				}
                if(sum>M) {
					break;
				}
			}
		}
		
		System.out.println(count);
	}
}

 

---

2. 투 포인터 기법

이중 for문은 최악의 경우 시간 복잡도가 O(N^2)이므로, 투 포인터 기법을 이용하여 O(N)의 시간 복잡도로 풀이할 수 있다.

 

부분 수열의 왼쪽 인덱스를 low, 오른쪽 인덱스를 high라 할 때, low부터 high까지 부분 합 sum에 대해 sum<M이면 high를 증가시키고 sum>M이면 low를 증가시킨다.

 

high가 배열의 끝에 도달했을 때 sum>M이라면 low를 배열의 끝까지 하나씩 증가시키고, sum<M이라면 더 탐색할 필요가 없으므로 반복문을 종료한다.

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[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		int low=0;
		int high=0; 
		int sum=0; 
		int count=0;
		
		while(true) {
			if(sum>=M) {
				sum -= arr[low++];
			}
			else if(high==N) {
				break;
			}
			else {
				sum += arr[high++];
			}
			
			if(sum==M) {
				count++;
			}
			
		}
		System.out.println(count);
	}
}

위: 투 포인터 기법/아래: 이중 for문

투 포인터 기법이 조금 더 빠르다.