[BOJ] 15565 귀여운 라이언 - JAVA

1. 문제

15565번: 귀여운 라이언

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.

---

2. 풀이

1.  boolean배열에 라이언이라면 true, 어피치라면 false를 저장한다.

2.  초기값으로 min = N+1, ryan = 첫번째인형이 라이언이라면 1, 아니면 0을 저장한다.

3.  l = 0, r=1로 시작한다.

4.  만약 ryan이 K보다 크거나 같으면 최솟값을 갱신한다. l++하고 ryan수도 변경한다.

5.  만약 r>=N이라면 l++해야한다. 이에 맞춰 ryan수를 변경한다.

6.  4,5의 경우가 아니면서 toy[r]이 라이언이라면 개수를 늘린다. r++한다.

7.  마지막으로 min을 출력한다. 이 때, min이 초기값 N+1과 같다면 -1을 출력한다.

 

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

public class BOJ_15565_귀여운라이언 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());
      boolean[] toy = new boolean[N];
      st = new StringTokenizer(in.readLine());
      for (int i = 0; i < N; i++) toy[i] = st.nextToken().equals("1");

      int min = N + 1, ryan = toy[0] ? 1 : 0;
      int l = 0, r = 1;
      while (l < r) {
         if (ryan >= K || r >= N) {
            if(ryan >= K) min = Math.min(min, r - l);
            if (toy[l++]) --ryan;
         } else if (toy[r++]) {
            ++ryan;
         }
      }

      if (min == N + 1) System.out.println(-1);
      else System.out.println(min);
   }
}

---

3. 결과

조건을 제대로 보지 않아서 두번정도 틀리고, r범위때문에 또 여러 번 틀렸다.

이제 투포인터는 당분간 풀지 않을 예정이다 ! 다른 알고리즘 풀다가 다시 오는 게 좋을 것 같다.