[baekjoon] 9489 사촌 - 메모리 초과/NoSuchElement

내가 힘들었던 것

• 문제를 잘 이해하자.
  • 해당 문제는 부모의 형제의 자식들의 수를 정확하게 세는 것이 정답이다.(깊이만 같다고 해서 부모 형제가 아니다.)
• NoSuchElement
  • 항상 input 메서드로 입력값을 세팅해주는데 제대로 다 받지도 않고 return을 시켜버려서 해당 예외가 발생했다.
• 메모리를 효율적으로 
  • 꼭 숫자 자체를 index로 둘 필요없이 다른 배열에 숫자를 저장하는 배열을 두고 해당 index에 들어있는 숫자로 사용하면 된다. 아래 두 코드를 비교해보면 된다.

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

public class Main {
  public static int[] pArr = new int[1_000_001];
  public static int[] arr;
  public static int[] childCount = new int[1_000_001];
  public static int N, K;


  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    while(true){
      input(br);
      if(N == 0) break;
      pro();
    }
  }

  static void pro()  {
    if(N <= 1 || K == arr[0]) {
      System.out.println(0);
      return;
    }
    int p = pArr[K];
    if(p == arr[0]){
      System.out.println(0);
      return;
    }
    int pp = pArr[p];
    int count = 0;
    for(int i = 1; i < arr.length; i++){
      int cur = arr[i];
      if(pArr[cur] == pp && cur != p){
        count += childCount[cur];
      }
    }
    System.out.println(count);
  }

  static void input(BufferedReader br) throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    if(N==0) return;
    arr = new int[N];
    st = new StringTokenizer(br.readLine());

    for(int i=0 ; i<N ; i++){
      arr[i] = Integer.parseInt(st.nextToken());
    }
    for(int i=0 ; i<1_000_001 ; i++){
      pArr[i] = 0;
      childCount[i] = 0;
    }
    if(N == 1) return;

    int parentIdx = 0;
    int p = arr[parentIdx];
    childCount[p]++;
    pArr[arr[1]] = p;
    for(int i=2 ; i<N ; i++){
      int c = arr[i];
      if(arr[i-1] != c -1) parentIdx++;
      p = arr[parentIdx];
      childCount[p]++;
      pArr[c] = p;
    }
  }

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

public class Main {
  public static int N;
  public static int K;
  public static long result = 0;
  public static int[] arr;
  public static int[] parents;
  public static int[] childCount;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    while(true){
      input(br);
      if(N==0) {
        break;
      }
      pro();
      System.out.println(result);
    }
  }
  public static void input(BufferedReader br) throws Exception{
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    if(N==0) return;
    arr  = new int[N];
    parents = new int[N];
    childCount = new int[N];
    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < N; i++){
      int num = Integer.parseInt(st.nextToken());
      arr[i] = num;
    }

    parents[0] = -1;

    int parent = -1;
    for (int i = 1; i < N; i++) {
      parent++;
      childCount[parent]+=1;
      parents[i] = parent;
      while(i+1 < N && arr[i+1] == arr[i]+1){
        i++;
        childCount[parent]+=1;
        parents[i] = parent;
      }
    }
  }

  public static void pro(){
    int idx = 0;
    while(arr[idx] != K) idx++;

    int parent = parents[idx];
    if(parent == -1) {
      result = 0;
      return;
    }

    int pp = parents[parent];
    result = 0;
    for(int i=0 ; i<parents.length ; i++){
      if(parents[i] == pp && parent != i) result += childCount[i];
    }
  }
}

1000001 배열을 초기화 해주는 부분이 사라져서 아래 코드가 1908ms -> 908ms로 더 빠르다.