[Java] 백준 귀여운 라이언

1. 문제 분석

문제는 정말 간단한데 구현하는데 짜증이 좀 난 문제다.

투포인터 문제인건 알았지만 그 전에 그냥 for문으로 구현을 해보았다.

당연히 시간초과가 난다. 이제 투포인터로 풀어보자..

(문제에서 값이 없는 경우는 -1을 표시해줘야 한다고 한다. 문제좀.. 보자..)

 

나는 여기서 투포인터 알고리즘을 활용한 슬라이딩 윈도우를 사용했다.

간단하게 설명하면 특정범위를 한칸씩 옮겨가며 값을 확인하는 방법이다.

 

입력값으로 배열의 크기와 몇개를 포함해야하는지 알려줬으므로 라이언 인형일 때 인덱스를 구해둔다.

테스트케이스 1은 현재 0, 4, 6, 9가 된다.

즉 구하는 것은 (0, 4, 6), (4, 6, 9)만 구하면 끝이다. 이렇게 간단한 문제를 제대로 안읽어서 고생을 했다..

2. 구현

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int size = Integer.parseInt(st.nextToken());
        int doll = Integer.parseInt(st.nextToken());
        int[] arr = new int[size];
        ArrayList<Integer> list = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] == 1) {
                list.add(i);
            }
        }

        int set = Integer.MAX_VALUE;
        int start = 0, end = doll - 1;

        if(list.size() < doll){
            System.out.println(-1);
            return;
        }

        while (true) {
            if (end == list.size()) {
                break;
            } else {
                set = Math.min(set, list.get(end) - list.get(start) + 1);
                start++; end++;
            }
        }
        if(set == Integer.MAX_VALUE){
            System.out.println(-1);
        }
        else{
            System.out.println(set);
        }
    }
}

나는 여기서 ArrayList에 라이언 인형 인덱스를 넣어주었다.

만약 리스트의 크기가 내가 구하고자하는 인형의 범위보다 작다면 당연히 구할 수 없는 것 이므로 -1을 출력한다.

 

구할 수 있다면 투포인터를 사용한다.

start와 end는 구할려고 하는 범위고 범위를 구했다면 1씩 더해서 다른 범위를 구하면 끝이다.

3. 마무리

문제좀 읽자.. 디버깅 해보면서 분명 조건은 다 맞는데 왜 안나오지 싶어서 봤더니 -1을 출력하라고 한다..