[백준, Java] 15565번, 귀여운 라이언(슬라이딩 윈도우)

문제 링크

15565번: 귀여운 라이언

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 라이언 인형은 1, 어피치 인형은 2로 표현됩니다.

2. 라이언 인형이 K개 이상 있는 가장 작은 연속된 집합의 크기를 결과로 출력합니다.

3. K개의 라이언 인형을 만족하는 집합이 없으면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 슬라이딩 윈도우를 통해서 최소 크기를 구합니다.

 

3. 최소 크기를 결과로 출력합니다.

 

 

슬라이딩 윈도우

 

문제에서 필요한 것은 라이언 인형의 개수이다.

 

즉, 어피치 인형의 위치는 상관없이 라이언 인형의 위치만 이용하면 결과를 구할 수 있습니다.

 

각 라이언의 위치를 저장한 뒤,

 

첫 번째 라이언부터 탐색하면서 최소 크기를 구합니다.

 

테스트 케이스 진행하는 과정을 보시면 한 눈에 이해하실 수 있을 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 10

 

K : 3

0	1	2	3	4	5	6	7	8	9
1	2	2	2	1	2	1	2	2	1

 

2. 슬라이딩 윈도우를 통해서 최소 크기를 구합니다.

 

라이언의 위치만 따로 표시하면

 

0	4	6	9
1	1	1	1

 

1번째 라이언 → 3번째 라이언의 크기 : 6 - 0 + 1 : 7개

2번째 라이언 → 4번째 라이언의 크기 : 9 - 4 + 1 : 6개

3번째 라이언 → 5번째 라이언(X) : 더 이상 조건에 만족하는 집합을 만들 수 없다.

 

3. 최소 크기를 결과로 출력합니다.

 

2번째 라이언 → 4번째 라이언의 크기 : 9 - 4 + 1 : 6개

 

 

최소 크기 6을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 인형의 정보를 띄어쓰기 기준 구분합니다.
• 라이언의 위치만 저장하는 List<>을 구성합니다.
• 첫 번째 라이언부터 K개를 가지는 집합의 크기를 계산합니다.
• 라이언의 개수가 K보다 작으면 -1을 BufferedWriter 저장합니다.
• 라이언의 개수가 K보다 크면 최소 크기를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        List<Integer> list = new ArrayList<>();	//라이언 인형 위치 저장 리스트
        st = new StringTokenizer(br.readLine()," ");
        //인형 정보 저장
        for(int i=0;i<N;i++){
            int n = Integer.parseInt(st.nextToken());
            if(n == 1){		//라이언 인형일 때
                list.add(i);
            }
        }
        //라이언 인형의 개수가 K보다 작을 때
        if(list.size()<K){
            bw.write("-1");
        }else{		//라이언 이형의 개수가 K 이상일 때
            int result = Integer.MAX_VALUE;
            //첫 번째 라이언부터 탐색 진행
            for(int i=0;i<=list.size()-K;i++){
                int start = list.get(i);
                int end = list.get(i+K-1);
                result = Math.min(result, end-start+1);
            }
            //최소 크기 BufferedWriter 저장
            bw.write(String.valueOf(result));
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}