BOJ 1818 - 책정리 링크
(2023.07.18 기준 G2)

문제

1번부터 N번까지 숫자로 표현되는 책들이 N권이 있다. 이 책들이 배열된 순서가 주어지는데, 이를 오름차순으로 재배열해야 한다. 어떠한 책 하나를 꺼내서 원하는 다른 위치에 꽂을 수 있는데, 이 행동을 해야 하는 최소 횟수 출력

알고리즘

LIS (O(n log n))

풀이

책은 내가 원하는 아무 위치에 꽂을 수 있다. 그렇다면, 이미 배열 조건을 만족하는 책들을 최대한 제외하여 행동을 해야 한다.
책들은 오름차순으로 정렬되어야 하기 때문에, 결국은 이미 배열 조건을 만족하는 책들은 최장 증가 부분 수열이며 이들을 제외한 나머지 원소(책)의 개수가 답이 된다.

그런데 N이 최대 200,000이라서 O(n log n) 방법을 사용해야 한다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;

int N, A[MAXN];

struct LIS{
    int I[MAXN], idx;
    vector<int> L;

    void init();

    void trace(){ // 역추적하여 실제 LIS를 출력
        int result[idx];
        for (int i = N - 1; i >= 0; i--) if (I[i] + 1 == idx) result[--idx] = A[i];

        for (auto x: result) cout << x << ' ';
    }
}lis;

void LIS::init(){ // LIS를 구성하는 수열 A의 인덱스 및 LIS의 길이를 구한다.
    fill(I, I + N, 0); idx = 1;
    L.push_back(A[0]);

    for (int i = 1; i < N; i++){
        // 지금까지 저장된 수열의 최댓값보다 더 크면 수열의 길이가 늘어난다.
        if (L.back() < A[i]){
            I[i] = idx++;
            L.push_back(A[i]);
        }
        // 수열에 들어갈 수 있는 인덱스를 찾아 들어간다.
        else{
            I[i] = lower_bound(L.begin(), L.end(), A[i]) - L.begin();
            L[I[i]] = A[i];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];

    // 이미 오름차순을 이루고 있는 LIS의 책들을 제외한 책들만 재배치하면 된다.
    lis.init();
    cout << N - lis.idx;
}

• Python

import sys; input = sys.stdin.readline
from bisect import bisect_left

class LIS:
    def __init__(self): # LIS를 구성하는 수열 A의 인덱스 및 LIS의 길이를 구한다.
        self.I = [0] * N
        self.idx = 1
        self.L = [A[0]]

        for i in range(1, N):
            # 지금까지 저장된 수열의 최댓값보다 더 크면 수열의 길이가 늘어난다.
            if self.L[-1] < A[i]:
                self.I[i] = self.idx
                self.idx += 1
                self.L.append(A[i])
            # 수열에 들어갈 수 있는 인덱스를 찾아 들어간다.
            else:
                self.I[i] = bisect_left(self.L, A[i])
                self.L[self.I[i]] = A[i]

    def trace(self): # 역추적하여 실제 LIS를 출력
        self.result = [0] * self.idx
        for i in range(N - 1, -1, -1):
            if self.I[i] + 1 == self.idx:
                self.idx -= 1
                self.result[self.idx] = A[i]

        print(*self.result)

N = int(input())
A = list(map(int, input().split()))

# 이미 오름차순을 이루고 있는 LIS의 책들을 제외한 책들만 재배치하면 된다.
lis = LIS()
print(N - lis.idx)