[BOJ] 15565 귀여운 라이언

귀여운 라이언

풀이

• K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합 크기를 출력하라 이기 때문에 "투 포인터" 라고 생각했다.
• 근데 시간초과 났다...

  🙅‍♀️ 시초 난 코드

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          int N = Integer.parseInt(st.nextToken());
          int K = Integer.parseInt(st.nextToken());
          int[] arr = new int[N];
          st = new StringTokenizer(br.readLine());
          for(int i=0;i<N;i++){
              arr[i] = Integer.parseInt(st.nextToken());
          }
          int answer = 0;
          for(int size=K;size<N;size++){
              int lion = 0;
              for(int i=0;i<size;i++){
                  if(arr[i]==1) lion++;
              }
              if(lion>=K){
                  System.out.println(size);
                  System.exit(0);
              }
              else{
                  for(int next=size;next<N;next++){
                      if(arr[next]==1) lion++;
                      if(arr[next-size]==1) lion--;
                      if(lion>=K){
                          System.out.println(size);
                          System.exit(0);
                      }
                  }
              }
          }
      }
  }

• 2중 for문 때문에 시간초과가 나는 것 같았고, 그럼 for문을 하나로 어떻게 줄일까? 고민했다.
• 그래서 생각한 것! lion은 "1"로 나타내 지는데, 인형 정보를 입력받을 때 "1"의 index값을 ArrayList에 저장해두는 것이다. 그리고 나서, 그 index 값들을 이용해서 투포인터 형식을 사용하는 것이다.
  코드를 보겠다.

  🙆‍ 정답 코드

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          int N = Integer.parseInt(st.nextToken());
          int K = Integer.parseInt(st.nextToken());
          int[] arr = new int[N];
          st = new StringTokenizer(br.readLine());
          int answer = 0;
          ArrayList<Integer> list = new ArrayList<>();
          for(int i=0;i<N;i++){
              arr[i] = Integer.parseInt(st.nextToken());
              if(arr[i]==1) list.add(i);
          }
          int start = 0,end=K-1;
          int min = Integer.MAX_VALUE, cnt=0;
          if(list.size()<K){
              System.out.println(-1);
          }
          else{
              while(true){
                  if(end==list.size()) break;
                  cnt = list.get(end)-list.get(start)+1;
                  min = Math.min(min,cnt);
                  start++;
                  end++;
              }
              System.out.println(min);
          }
      }
  }

  • 예제 입력이 이렇다고 하자.

    10 3	
    1 2 2 2 1 2 1 2 2 1

  • 그렇다면 ArrayList에 저장되는 값은 [0,4,6,9] 일 것이다.
  • while문을 보자. int start =0, end= K-1 로 초기값을 설정했는데, 만약에 예제 입력처럼 K=3 으로 라이언이 최소 3개 포함되어야 한다고 하자. ArrayList의 Index는 0부터 시작하므로, end=K-1 로 해주어야 집합의 크기를 구할 때, 즉 cnt= list.get(end)-list.get(start)+1 의 식이 성립할 수 있게 된다.
  • start, end를 1씩 늘리면서, end가 list 끝까지 도달하면 while문을 탈출한다. 이 부분이 투포인터!
  • 그리고 min = Math.min(min,cnt) 로, 해당 집합의 크기가 최소인지 계속 비교한다.

• 풀이를 생각해낸 내가 조금 뿌듯했던 문제...까먹지말고 다음엔 정답 풀이로 처음부터 풀었으면 좋겠다