[백준] 15565번 - 귀여운 라이언(JAVA)

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

15565번: 귀여운 라이언

 

- 문제 -

 

---

- 풀이 과정 -

연속된 인형 들에서 라이언 인형(1)이 k개이상 만큼 포함되는 범위의 크기를 구하면 되는 문제입니다. 그러나 라이언 인형(1)이 포함되는 범위 중 가장 작은 범위의 크기를 구해야 하기에 k개이상이 아닌 k개가 되는 범위만 추려주면 됩니다.

 

연속된 숫자의 범위에서 답을 구하는 문제인 만큼 sliding window기법을 사용하여 풀어줄 수 있습니다.

연속된 수를 배열로 저장 후 1이 k개가 되는 범위를 지정해줍니다. 문제에서 k=3이기에 1의 개수가 3개인 범위를 지정합니다.

범위를 지정 후 범위 내의 크기를 구해주고 다음 1의 위치로 이동해서 다시 범위의 크기를 지정하는 식으로 하면 문제를 풀 수 있습니다.

그러나 이렇게 하면 범위를 이동할 때마다 범위의 크기를 다시 구해야 하는 단점이 있기에 해당 방식이 아닌 ArrayList를 이용해 다른 방식으로 풀었습니다.

 

지정된 범위의 개수는 배열의 index 번호와 관련이 있습니다. index 0 ~ 6의 개수를 구하는 경우 범위 끝(end:6)-범위 시작(start:0)+1의 식을 적용하면 해당 범위의 원소 개수를 구할 수 있습니다. 따라서 1이 담겨있는 배열의 index만 따로 추려 ArrayList에 저장합니다.

라이언 인형(1)의 위치만 저장되어 있는 ArrayList에서 k의 값만큼 window범위를 지정합니다. end-start+1의 식을 적용하면서 window이동 시 마다 결과 값을 비교하여 가장 작은 값을 출력합니다.

 만약 ArrayList의 크기가 k개 보다 작다면 -1을 출력해주고 프로그램을 종료시키면 됩니다.

---

- 소스 코드 -

package com.test;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main { 
    
    // 15565번 - 귀여운 라이언
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] input=br.readLine().split(" ");
        int[] doll=new int[Integer.parseInt(input[0])]; //인형들의 배열
        int k=Integer.parseInt(input[1]);   //라이언 인형 포함 갯수
        ArrayList<Integer> lion=new ArrayList<Integer>();   // 라이언 인형의 위치를 저장할 리스트
        
        input=br.readLine().split(" ");
        for(int i=0;i<doll.length;i++) {
            doll[i]=Integer.parseInt(input[i]);
            if(doll[i]==1) lion.add(i);     //인형이 라이언인경우 위치를 저장
        }
        
        if(lion.size()<k) { //라이언 인형의 개수가 k보다 적은 경우 -1호출 후 종료
            System.out.println(-1);
            return;
        }
        
        /*
            int min=Integer.MAX_VALUE ,end=k-1;
            for(int start=0;(start+end)<lion.size();start++) {
                min=Math.min(min, lion.get(start+end)-lion.get(start)+1);
            }        
         */
        int start=0,end=k-1;    // (슬라이딩)윈도우 사이즈 지정
        int min=Integer.MAX_VALUE, cnt=0;
        while(true) {
            if(end==lion.size()) break;
            cnt=lion.get(end)-lion.get(start)+1;
            min=Math.min(min, cnt);
            
            start++;
            end++;
        }
        
        System.out.println(min);
    }
}

 

[참고 사이트]

https://paris-in-the-rain.tistory.com/115

https://hidelookit.tistory.com/179