백준 15565 - (Java) 귀여운 라이언

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

15565번: 귀여운 라이언

1. 유형

투포인터

 

2. 문제 분석

 

시뮬레이션

 

위와 같이 시뮬레이션을 돌리면 푸는것이 가능합니다.

오른쪽이 증가하는 중(rflag == true)이면, 합을 감소시키고, 길이를 갱신

그리고 왼쪽 포인터를 증가시키기 위해 lflag=true를 시켜줍니다.

 

---

2번째 풀이

위 처럼 구하면 코드도 더럽고, 변수도 많이 필요합니다.

 

그래서 라이언의 인덱스만 따로 리스트에 저장.

 

그러면  {0, 4, 6, 9}가 나오고,

 

여기서 K개만큼 슬라이딩 윈도우를 하게되면, 위 보다 쉽게 푸는것이 가능합니다.

 

3.코드

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(in.readLine());
		int N=stoi(st.nextToken());
		int K=stoi(st.nextToken());
		int arr[]= new int[N];
		st=new StringTokenizer(in.readLine());
		for(int i=0;i<N;i++) {
			arr[i]=stoi(st.nextToken());
		}
		int INF = Integer.MAX_VALUE;
		int l=0,r=0,sum=0, len, ans=INF;
		boolean lflag=false, rflag=true;
		for(int i=0;i<N;i++) {
			if(arr[i]==1) {
				l=i;
				r=i;
				break;
			}
		}
		while(r<N && l<N) {
			if(rflag && arr[r]==1) {
				sum++;
				if(sum==K) {
					rflag=false;
					lflag=true;
					sum--;
					len=r-l+1;
					ans=Math.min(len, ans);
				}
			}
			else if(lflag && arr[l]==1) {
				lflag=false;
				rflag=true;
			}
			if(lflag) {
				l++;
			}else
				r++;
		}
		if(ans==INF)
			System.out.println(-1);
		else
			System.out.println(ans);
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}