[JAVA]백준 2631번: 줄세우기

www.acmicpc.net/problem/2631

2631번: 줄세우기

1. 문제 설명

 

1번부터 N번까지의 학생들이 순서대로 있지 않을 때 번호 순서대로 만들기 위해서 학생들을 이동시키는 최소 이동 개수 구하는 문제이다.

 

2. 풀이

 

LIS 알고리즘을 이용하여 풀 수 있다.

 

이미 순서대로 있는 아이들은 옮길 필요가 없고 순서대로 있지 않은 아이들만 옮기면 되기 때문에 LIS 알고리즘을 이용하여 최장 증가 부분 수열의 길이를 구하고 총 학생 수에서 수열의 길이를 빼면 된다.

 

 

LIS 알고리즘은 이분 탐색을 이용하여 풀었는데 (O(NlogN)) 자세한 내용은 kwoncorin.tistory.com/67?category=939904 아래 문제를 참고하면 된다.

 

3. 코드

 

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int num = Integer.parseInt(br.readLine());


        int[] store = new int[num];

        int end = 1;

        store[0] = Integer.parseInt(br.readLine());

        for (int x = 1; x < num; x++) {
            int temp = Integer.parseInt(br.readLine());

            int left = 0, right = end;

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

                if (store[mid] < temp) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            store[right]=temp;

            if(right==end)
                end++;


        }

        bw.write(String.valueOf(num - end) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }


}