[코테] 백준 1818 책정리

문제

동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 오른쪽으로 순서대로 1∼N번의 책들로 재배열하길 원한다.

동혁이가 책들을 배열하는 방법은 어떠한 책 하나를 꺼내서 다른 위치에 꽂는 방법이다.

1 5 2 3 4

위와 같이 책이 배열되어 있을 때 5번 책을 꺼내 가장 뒤쪽에 꼽으면

1 2 3 4 5

로 배열되고, 1∼5번까지 순서대로 책이 꽂히면서 정리는 끝나게 된다.

문제는 현재 책들의 배열순서가 주어지면 최소 횟수로 책들을 옮겨 책 정리를 끝내는 것이다.

---

입력

첫째 줄에 책의 개수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄에는 현재 책들이 배열된 순서가 공백으로 구분되어 주어진다.

---

출력

동혁이가 책들을 옮겨야 하는 최소 횟수를 출력한다.

예제 입력 1

5
2 1 4 5 3

예제 출력 1

2

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 백준_1818_책정리 {

  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    List<Integer> array = new ArrayList<>();

    array.add(0);

    for(int i = 0; i < N; i++) {
      int number = sc.nextInt();
      if(array.get(array.size() - 1) > number) {
        array.set(getLowerBound(number, array), number);
      } else {
        array.add(number);
      }
    }

    System.out.println(N - array.size() + 1);
  }

  public static int getLowerBound(int number, List<Integer> array) {
    int left = 0;
    int right = array.size();

    while(left < right) {
      int mid = (left + right) / 2;

      if(array.get(mid) <= number) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return left;
  }
}