문제 풀이

가장 큰 수의 위치부터 배열의 시작까지 이동하면서 제대로 정렬 되어있는 수의 개수는 몇개인지 찾으면 나머지 숫자는 무조건 이동해야한다.

예를들어, 입력이 n=5이고 4 1 5 2 3이라면 4와 5는 이동할 필요가없다. 1, 2, 3만 이동하면된다. 즉 순서를 잘 정해서 3번을 이동시키면된다.

또 다른 예로, 입력이 n=6이고 5 2 1 3 4 6이라면 6과 5는 올바르게 정렬되어있다. 그러면 나머지 2, 1, 3, 4를 순서를 잘 정해 이동시키면 4번만에 정렬될 수 있다.

그렇다면 핵심은 최대값의 위치부터 인덱스가 작아지면서 값이 1씩 작아지는 수열의 길이를 구하면 된다.

문제 링크

boj/2872

소스코드

PS/2872.java

import java.io.*;


public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        int dp[] = new int[n];
        int max = n;
        int max_idx = -1;
        int len = 1;
        for(int i=0;i<n;i++)
        {
            arr[i] = Integer.parseInt(br.readLine());
            if (arr[i] == n)
                max_idx = i;
        }
        for(int i = max_idx;i >=0;i--)
        {
            if(arr[i] == max-1)
            {
                max--;
                len++;
            }
        }
        bw.write(Integer.toString(n - len));
        bw.flush();
    }
}