[코드트리] 수열의 순서 바꾸기

어려움 문제는 확실히 난이도가 높다........ 화이팅..

 

---

 

1이상 N이하의 숫자가 겹치지 않게 구성된, 원소의 개수가 N개인 수열이 하나 주어졌을 때, 맨 앞에 있는 숫자를 선택해 수열 중간에 집어넣는 행동을 최소 몇 번 반복해야 숫자들이 오름차순 정렬이 되는지를 계산하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에는 N이 주어집니다.

두 번째 줄에는 N개의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ N ≤ 100

출력 형식

첫 번째 줄에 수열을 오름차순으로 정렬하기 위해 맨 앞에 있는 원소를 뒤로 밀어 넣어야 하는 최소 횟수를 출력합니다.

 

입출력 예제

예제1

입력:

4
1 2 4 3

출력:

3

 

예제 설명

처음 숫자 1을 4와 3 사이로 옮기면 2 4 1 3이 됩니다.

그 다음 숫자 2를 1과 3 사이로 옮기면 4 1 2 3이 됩니다.

최종적으로 숫자 4를 맨 뒤로 옮기면 1 2 3 4가 되므로 오름차순으로 정렬하기 위해서는 숫자를 3번 뒤로 보내야 합니다.

 

---

Intuition

주어진 수열에서 뒷부분에 있는 정렬된 부분을 제외하고, 그 외의 앞부분을 뒤의 적절한 자리에 잘 삽입하면 됩니다.주어진 수열에서 뒷부분에 있는 정렬된 부분을 제외하고, 그 외의 앞부분을 뒤의 적절한 자리에 잘 삽입하면 됩니다.

 

Algorithm

정렬되지 않은 앞부분의 원소들을 정렬된 뒷부분 사이사이에 적절히 끼워넣으면 되므로, 답은 정렬되어 있지 않은 원소의 개수가 됩니다.
따라서, 뒤에서부터 보며 정렬되어 있지 않은 순간을 잡아 그 앞에 있는 원소의 개수가 답이 됩니다.

 

---

코드

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 100;
    
    public static int n;
    public static int[] blocks = new int[MAX_N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력:
        n = sc.nextInt();
        for(int i = 0; i < n; i++)
            blocks[i] = sc.nextInt();
        
        // 맨 뒤에 있는 숫자들이 
        // 정렬된 상태로 가장 길게 놓여져 있는 것이 좋습니다.
        // 예를 들어 1 3 6 5 2 4 7 라는 수열이 있다면
        // 2 4 7은 이미 정렬되어 있으므로
        // 앞에 있는 1 3 6 5만 각 위치에 잘 옮겨주면 됩니다.
        // 따라서 4가 됩니다.

        // 즉, 뒤에서부터 보며
        // 정렬되어 있지 않은 순간을 잡아
        // 그 앞에 있는 원소는 전부 옮겨주면 됩니다.

        int idx = n - 2;
        while(idx >= 0 && blocks[idx] < blocks[idx + 1])
            idx--;

        System.out.print(idx + 1);
    }
}