StepByStep #inversion

[hwangnk1004]

• 문제 http://59.23.150.58/30stair/inversion/inversion.php?pname=inversion

  • 1 부터 n 까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1 부터 n 까지 각각의 수 앞에 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 inversion sequence 라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1 앞에 놓인 1 보다 큰 수는 4 , 8 , 6 , 2 , 5 로 5 개이고 , 2 앞에 놓은 2 보다 큰 수는 4 , 8 , 6 으로 3 개 3 앞에 놓인 3 보다 큰 수는 4 , 8 , 6 , 5 로 4 개 따라서 4 8 6 2 5 1 3 7 의 inversion sequence 는 5 3 4 0 2 1 1 0 이 된다. n 과 1 부터 n 까지의 수를 사용하여 이루어진 수열의 inversion sequence 가 주어졌을때 원래의 수열을 출력하는 프로그램을 작성하시오.

• 답

import java.util.Scanner;

public class Main { public static void main(String args[]) {

    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();

    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = scanner.nextInt();
    }
    int oriArr[] = new int[n];
    int count = -1;
    int ans = 0;
    int x = 0;

    while (true) {

        for (int i = 0; i < n; i++) {

            if (oriArr[i] == 0) {
                count++;
            }

            if (count == arr[ans]) {
                oriArr[i] = ans++ + 1;
                count = -1;
                x++;
                break;
            }
        }

        if (x ==n ) {
            for(int i=0; i<n; i++) {
                System.out.print(oriArr[i]+ " ");
            }
            break;
        }
    }

}

}