[백준] 14465 소가 길을 건너간 이유 5 - 투포인터(Two Pointer) JAVA

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

코드설명

투포인터(Two Pointer) 를 활용합니다.

 

처음 문제를 보고 파라매트릭 서치인가? 라는 생각이 들었습니다.

하지만, 문제를 보면 연속된 K라는 조건이 주어지므로 투포인터로 O(N) 의 시간복잡도로 풀 수 있다는 것을 알 수 있습니다.

사실 N의 범위가 나오지 않아서 좀 애매하긴 하지만, 빠르게 풀수록 좋습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, B;
	static int answer = 0;
	static int[] arr;
	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());
		K = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		answer = N - B;
		Arrays.fill(arr, 1);
		for(int i=0;i<B; i++) {
			st = new StringTokenizer(br.readLine());
			arr[Integer.parseInt(st.nextToken()) - 1] = 0;
		}
		
		answer = twoPointer();
		System.out.println(answer);
	}
	
	static int twoPointer() {
		
		int signalPillow = 0;
		for(int i=0;i<K-1;i++) {
			signalPillow += arr[i];
		}
		
		for(int i=K-1; i<N; i++) {
			signalPillow += arr[i];
			//몇개를 고쳐야하는가?
			answer = Math.min(answer, K - signalPillow);
			signalPillow -= arr[i - (K - 1)];
		}
		
		return answer;
	}
	
}