문제

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

Silver IV

코드 (Java)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] ori_arr = new int[n];
        int[] arr = new int[n];
        int[] cnt = new int[n];
        boolean[] is_final = new boolean[n];

        for (int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(sc.next());
            ori_arr[i] = arr[i];
        }
        sc.nextLine();

        Arrays.sort(arr);

        for (int i = 0; i < n; ++i) {
            int min = arr[i];
            boolean selected_final = false;
            for (int j = 0; j < n; ++j) {
                if (is_final[j]) {continue;}
                else if (selected_final) {cnt[j] += 1;}
                else if (ori_arr[j] == min) {
                    is_final[j] = true;
                    selected_final = true;
                } else {cnt[j] += 1;}
            }
        }

        for (int i = 0; i < n; ++i) {
            System.out.printf("%d ", cnt[i]);
        }

        sc.close();
    }
}

풀이

문제가 이해가 국어 이슈(...)로 인해 좀 난해했다.

요약하면 정렬시 각 원소들의 index가 뭔지를 물어보는 것이다. 동일 크기 원소는 자기들끼리 위치가 바뀔 수 있어서 여러 조합이 가능하면 사전순으로 가장 빠른 조합을 고르라고 했다.

n의 크기가 작아서, 순회하는 형식으로 cnt를 늘려 최종 idx를 계산하는 방식을 택했다.

더이상 업데이트 안해도 되는가 -> is_final로 추적
(동일 원소 대비) 이미 final로 정해진 애가 있는가 -> selected_final로 추적