[백준/Java] 1818 : 책정리

📌 문제 정보

• 번호: 1818
• 제목: 책정리
• 난이도: Gold 2
• 분류: 이분탐색, 가장 긴 증가하는 부분 수열(LIS)

---

💡 접근 방식

최소 횟수로 책을 정렬하는 문제입니다.
움직이지 않아도 되는 책의 최대 개수 = LIS의 길이이므로
정답 = N - LIS 길이입니다.

---

🔹 1단계 – 핵심 관찰

이미 올바른 순서로 놓인 책들은 움직일 필요가 없음

2 1 4 5 3

LIS = [1, 4, 5]  길이 3
→ 1, 4, 5는 그대로 두고 2, 3만 이동
→ 정답 = 5 - 3 = 2

처음에는 1부터 시작하는 LIS만 유효하다고 생각했는데 일반 LIS가 맞았음

3 4 5 1 2

1부터 시작 LIS: [1, 2]  → 5 - 2 = 3  ← 틀림
일반 LIS:       [3, 4, 5] → 5 - 3 = 2  ← 맞음

---

🔹 2단계 – LIS 이분탐색

tails[i] = 길이 i+1인 LIS의 마지막 원소 중 최솟값

arr = [2, 1, 4, 5, 3]

2 → tails = [2]
1 → tails = [1]          // 2 자리에 1 교체
4 → tails = [1, 4]
5 → tails = [1, 4, 5]
3 → tails = [1, 3, 5]    // 4 자리에 3 교체

LIS 길이 = 3

---

💻 핵심 코드

if (size == 0 || tails[size - 1] < num) {
    tails[size++] = num;
} else {
    int lo = 0, hi = size;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (tails[mid] < num) lo = mid + 1;
        else hi = mid;
    }
    tails[lo] = num;
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N×logN)
  • 원소마다 이분탐색 O(logN), N번 반복
• 공간 복잡도: O(N)

---

📄 전체 코드

package B1818;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] tails = new int[N + 1];
        int size = 0;

        for (int i = 0; i < N; i++) {
            int num = arr[i];

            if (size == 0 || tails[size - 1] < num) {
                tails[size++] = num;
            } else {
                int lo = 0, hi = size;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    if (tails[mid] < num) lo = mid + 1;
                    else hi = mid;
                }
                tails[lo] = num;
            }
        }

        System.out.println(N - size);
    }
}