[ALGO#11] 백준_2018_실버5_수들의 합5 : 투포인터 [JAVA]

문제 링크

2018번: 수들의 합 5

투포인터란?

투포인터 알고리즘은 슬라이딩 윈도우라고 불리기도 한다. N의 값이 매우 커서 완전 탐색 방식으로 풀면 시간 초과가 날 때 투포인터를 풀면 O(N)으로 풀 수 있다, 

1차원 배열이 있고, 배열 안에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 설정한다. 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘

 

접근법

sum 값을 비교해서 원하는 값보다 큰 경우, 작은 경우, 같은 경우를 분기해서 start, end 인덱스를 증감해주면 된다.

 

주의

start, end 인덱스 중 start 인덱스까지 배열의 마지막 인덱스에 도착하면 된다고 처음에 생각했는데 증감 값으로 초기화 되어있어서 end 인덱스만 배열의 끝에 도착하면 되었다. 대신 start가 마지막 인덱스에 도착할 때 원래 자기자신의 수가 빠지니 처음에 count를 1로 초기화해서 자기자신이 나오는 경우를 포함시켜야 한다.

 

비슷한 유형의 문제들

2003 : 수들의 합
1644 : 소수의 연속합
1806 : 부분합
2230 : 수 고르기
1484 : 다이어트
2038 : 골룽 수열
2531 : 회전 초밥
2096 : 내려가기
2293 : 동전1

 

성능 요약

메모리: 53668 KB, 시간: 208 ms

 

분류 :수학(math), 두 포인터(two_pointer)

 

 

전체코드(JAVA)

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N+1];
		// 배열 요소 1부터 초기화
		for (int i = 1; i <= N; i++) {
			arr[i] = i;
		}
		// 자기 자신
		int count = 1;
		int end = 1;
		int start = 1;
		//1부터 시작 (1인덱스 값이 1)
		int sum =1;
		// 뒤의 인덱스가 N이랑 같아진다면 끝까지 탐색한 것
		while(end != N) {
			// 현재 연속 합이 N과 같은 경우
			if(sum == N) {
				count++;
				end++;
				sum += arr[end];
			}else if(sum < N) { // 현재 연속 합이 N보다 작은 경우
				end++;
				sum += arr[end];
			}else {//sum > N // 현재 연속 합이 N보다 큰 경우
				sum -= arr[start];
				start++;
			}		
		}
		System.out.println(count);
	}
}

혹시 잘못된 정보나 궁금하신 내용이 있으시면 댓글로 남겨주시면 감사드리겠습니다.

 

공부자료
https://m.blog.naver.com/kks227/220795165570

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)