[백준OJ] 2631번 줄세우기

https://www.acmicpc.net/problem/2631

2631번: 줄세우기

---

 

풀이

최소한의 어린이만 움직여야 한다는 조건을 보고, 움직이지않아도 되는 아이들의 최댓값을 구한뒤, N값에서 빼면 되겠다 라는 생각을 했다.

이를 위해 이미 자기의 위치에 있는 아이들의 명수를 구하기위해 Lower_bound를 이용하여 가장긴 증가하는 배열의 길이를 구해준 뒤, N값에서 빼주었다. 이 방법으로 자신의 위치에 고정을 해도 되는 아이들을 제외한 나머지 아이들이 각자 자신의 자리를 찾아가면 되기때문이다.

 

시간복잡도

가장 긴 증가하는 배열의 길이를 구하기위해 Lower_bound를 구현하여 사용했다. Lower_bound함수는 O(logN)시간이 걸리므로, N명에 대해 Lower_bound함수를 적용해주면 O(NlogN)시간이 걸리게된다.

 

코드

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static int lower_bound(Vector<Integer> arr,int number){
        int i,middle,left,right;
        left=0;
        right=arr.size()-1;
        while(left<=right){
            middle=(left+right)>>1;
            if(arr.get(middle)>number){
                right=middle-1;
            }
            else if(arr.get(middle)<number){
                left=middle+1;
            }
        }

        return left;
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Vector<Integer> line = new Vector<>();

        for(int i=0;i<n;i++){
            int num=sc.nextInt();

            if(line.isEmpty()){
                line.add(num);
            }
            else{
                int index=lower_bound(line,num);
                if(line.size()<=index) line.add(num);
                else line.set(index,num);
            }
        }
        System.out.println(n-line.size());
    }
}