BOJ 15565 - 귀여운 라이언

 

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

15565번: 귀여운 라이언

 

 

• 인형 총 N개
• (라이언 인형 K개 어피치 인형 N-K개 ) 
• (1 ≤ K ≤ N ≤100만)
• 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기

 

 

아이디어

연속 부분 수열에 관한 문제이므로 투 포인터 알고리즘으로 먼저 접근해보았다.

 

L과 R 포인터를 설정한 후 R 포인터를 라이언 인형이 K개가 되도록 옮겨준 후 답을 갱신한다. 그 후 L 포인터를 다음 라이언 인형까지 옮겨준 후 또 R 포인터를 K개가 되도록 옮겨준 후 답을 갱신하는 과정을 반복하면 된다.

 

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, K;
    static int[] nums;

    static void init() 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());

        nums = new int[N + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        int R = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;

        for (int L = 1; L <= N; L++) {

            // L 포인터 옮기기 전 라이언 인형이었는지 체크
            if (nums[L-1] == 1) {
                sum--;
            }

            // R 포인터 옮기고 라이언 인형이면 sum++
            while (R + 1 <= N && sum < K) {
                R++;
                if (nums[R] == 1) {
                    sum++;
                }
            }

            // K개 이상일 경우 result 갱신
            if (sum == K) {
                result = Math.min(result, R - L + 1);
            }

        }

        // result 범위 체크 후 답 출력
        if (result > 0 && result <= N) {
            bw.write(result + " ");
        } else {
            bw.write(-1 + " ");
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }
}