백준 1015번 수열 정렬 JAVA

링크텍스트

설명

정수 배열 arr과 해당 인덱스를 저장할 index 배열을 생성한 후 index 배열을 arr의 값에 따라 정렬하였다. 이후 정렬된 index를 이용해 sequence 배열을 구성하고 출력하였다.
시간복잡도: O(NLogN), 공간복잡도: O(N)

코드

import java.util.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
	    
	    int n = Integer.parseInt(br.readLine());
	    int [] arr = new int[n];
	    Integer [] index = new Integer[n];
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i=0;i<n;i++){
	        arr[i] = Integer.parseInt(st.nextToken());
			index[i] = i;
	    }
	    
	    Arrays.sort(index, new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b){
				return arr[a] - arr[b];
			}
		});
	    
		int[] sequence = new int[n];
        for(int i=0; i<n; i++){
            sequence[index[i]] = i; 
        }

		for(int i=0; i<n; i++){
            sb.append(sequence[i]).append(" ");
        }
	    
		System.out.print(sb);
	}
}

참고 글

https://read-me.tistory.com/entry/JAVABOJ-1234-16