1. “연속된” 자연수의 합 구하기(백준 2018) - 투 포인터 활용

1. 정수 N 까지의 합 배열 만들기

S[i] = S[i-1] + A[i]

1. 구간합이 정수 N 과 같아지면 count++

// 강의듣기 전 내 풀이
import java.util.*;
public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int[] arr = new int[N+1];
		arr[0] = 0;
		int count = 0;
		
		for(int i = 1; i <= N; i++) {
			arr[i] = arr[i-1] + i;
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 1; j <= N; j++) {
				if(arr[j] - arr[i] == N) {
					count++;
				}
			}
		}
		
		System.out.println(count);
		
	}
}

❌❌ 시간 초과 ❌❌ → 중첩 for 문: 10000000 * 10000000

이러한 상황에서 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n) 의 시간 복잡도 알고리즘을 사용해야함

⇒ 이 경우 자주 사용하는 방법이 투 포인터

count 를 1로 초기화 하는 이유는, N 이 15일 때 숫자 15만 뽑는 경우의 수를 미리 초기화하는 것임

• 투 포인터 알고리즘의 시간복잡도가 O(n) 인 이유

start_index 와 end_index 모두 1 ~ N 까지 이동할 것임 ⇒ 2 * N ⇒ 시간복잡도는 상수 무시함 ⇒ 즉, O(n)의 시간복잡도를 갖는 것임

슈도 코드 작성

count = 1, start_index = 1, end_index = 1, sum = 1 초기화
// end_index 가 N 에 도착했을 때는 반복문을 종료하도록 설정했기 때문에 count = 1로 초기화
while(end_index != N) {
	if(sum == N) count 증가, end_index 증가, sum 에 end_index 값 더하기
	else if(sum > N) sum에서 start_index 값 빼기, start_index 증가
	else if(sum < N)  end_index 증가, sum에 end_index 값 더하기
}
count 출력

import java.util.*;
public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int count = 1;
		int start_index = 1;
		int end_index = 1;
		int sum = 1;
		
		while(end_index != N) {
			if(sum == N) {
				count++;
				end_index++;
				sum += end_index;
			} else if(sum > N) {
				sum -= start_index;
				start_index++;
			} else if(sum < N) {
				end_index++;
				sum += end_index;
			}
		}
		
		System.out.println(count);
	}
}