BOJ 1015 - 수열 정렬

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

1015번: 수열 정렬

 

1. 아이디어

 

1. 주어진 배열을 인덱스와 함께 정렬

 

2. 정렬된 배열의 인덱스 값을 P 배열에 저장

 

2. 시간 복잡도

정렬만 해주면 바로 P 배열을 채워줄 수 있으므로 정렬의 시간복잡도인 O(N log N) 만큼 걸린다.

N의 최댓값은 50이므로 1초안에 풀이가 가능하다.

 

 

 

3. 구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static Elem A[];

    static class Elem implements Comparable<Elem> {
        int num;
        int idx;

        @Override
        public int compareTo(Elem o) {
            return num - o.num;
        }
    };


    public static void main(String[] args) throws IOException {
        input();

        // 정렬
        Arrays.sort(A);

        // P 배열 채우기
        int[] P = new int[N];

        for (int i = 0; i < N; i++) {
            P[A[i].idx] = i;
        }

        for (int i = 0; i < N; i++) {
            bw.write(P[i]+" ");
        }

        bw.close();
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine(), " ");
        A = new Elem[N];
        for (int i = 0; i < N; i++) {
            A[i] = new Elem();
            A[i].num = Integer.parseInt(st.nextToken());
            A[i].idx = i;
        }

    }
}