[백준 / 골드3] 7570 줄 세우기 (Java)

문제 보기

사용한 것

• 연속 부분 증가수열의 크기를 구하는 LIS 알고리즘

풀이 방법

• LIS로 풀이하되, 그 중에서도 모든 수가 1씩 증가하는 수열이어야한다.
• 따라서 값을 저장하는 arr 배열과 인덱스를 저장하는 pos 배열을 사용한다.
• 현재값 + 1의 인덱스가 현재값보다 뒤라면 1씩 증가하는 LIS가 될 수 있음을 이용하여 구현한다.

코드

public class Main {

    private static int n;
    private static int[] arr;
    private static int[] pos;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(findMin());
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        pos = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            pos[arr[i]] = i;
        }
        br.close();
    }

    private static int findMin() {
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int len = 1;
            int val = arr[i];
            while (val < n) {
                if (pos[val + 1] < pos[val]) {
                    break;
                }
                val++;
                len++;
            }
            max = Math.max(len, max);
        }
        return n - max;
    }
}