15565 귀여운 라이언

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

15565번: 귀여운 라이언

투포인터라는 개념을 알고 있으면 쉽게 풀 수 있는 문제다. N이 10만이기 때문에 N^2의 탐색 방법을 사용하면 시간초과가 발생한다. 따라서 최대한 N에 가깝게 풀어야 한다.

이 문제에서는 범위를 최대한 넓게 탐색한 뒤에 조건을 만족한다면, 왼쪽부터 범위를 줄여가면서 최적해를 찾는다.

이 때, 범위를 1씩 줄이면서 답을 갱신하면 원하는 답을 얻을 수 있다.

 

정답 코드

import java.io.*;
import java.util.*;
public class Main {
   public static void main(String[] args) throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());

       int N = Integer.parseInt(st.nextToken());
       int K = Integer.parseInt(st.nextToken());
       final int INF = 1000001;
       int[] arr = new int[N];
       st = new StringTokenizer(br.readLine());
       for(int i = 0; i < N; i++){
         arr[i] = Integer.parseInt(st.nextToken());
       }
       int l = 0, r = 0, cnt = 0, len = 0, answer = INF;
       while(l < arr.length){
         if(cnt == K){ //조건을 만족한다면, 범위를 줄여가면서 최적해 탐색
           if(arr[l] == 1) {
             answer = Math.min(answer, len);
             cnt--;
           }
           l++;
           len--;
         }
         else if(r < arr.length){ //범위를 최대한 넓혀 탐색
           if(arr[r] == 1){
             cnt++;
           }
           r++;
           len++;
         }
         else{
           l++;
         }
       }
     System.out.println(answer == INF ? -1 : answer);
   }
}