문제 이해

숫자 배열이 주어지면, 이 배열을 비내림차순으로 정렬한다.
비내림차순은 항상 뒤의 숫자가 앞의 숫자보다 크거나 같은 수열을 의미한다.
(즉, 오름차순이지만 같은 숫자를 허용하는 배열)

정렬이 완료된 배열을 B, 원래 배열을 A라 하자.
이 때, A의 숫자가 B에서 어디에 위치해있는지 index를 출력하면 된다.

가능한 비내림차순 수열이 많을 경우 사전순으로 앞서는 것을 출력한다.

(ex1)
4 1 3 2 → 1 2 3 4로 정렬 가능하다.
정렬 후 4의 index는 3, 1의 index는 0, 3의 index는 2, 2의 index는 1이다.
따라서 <3 0 2 1>을 출력하면 된다.

(ex2)
1 1 2의 경우 <0 1 2>와 <1 0 2> 순서로 배열되어도 모두 비내림차순이다.
이 때 사전순으로 앞서는 것을 의미하기 때문에 <0 1 2>를 출력해야 할 것이다.

문제 풀이

여기서 생각보다 중요한 조건은 "사전 순으로 앞서는 것"이다.
똑같은 수 A,B가 존재하고, 정렬 이전에는 A가 B 앞에 존재했다.
그렇다면 정렬 이후에도 A가 B앞에 있어야 한다.
즉, 이 정렬 알고리즘은 Stable해야 함을 알 수 있다.

이를 구현하기 위해서는 JAVA의 Arrays.sort를 조금 더 자세히 살펴볼 필요가 있다.

배열은 2가지 형태로 구분할 수 있을 것이다.

1. Primitive 원소로 이루어진 배열 (ex) int[] arr

2. Object 원소로 이루어진 배열 (ex) Integer[] arr, A[] arr(A는 내가 지정한 Class)

이 때 Arrays.sort는 2가지 종류의 배열에 대해 다른 Sort 방법을 사용한다.

물론 2번에서 최악의 경우 Time Complexity가 차이나는 점도 중요하겠지만, 제일 중요한 것은 4번에 적힌 내용이다.
Primitive 배열은 In-place sort로써 메모리가 부족할 때 유용하며, Obejct 배열은 Stable Sort로 같은 값에 대해 순서를 보장해야 할 때 유용하다.
위 문제는 Stable sort이기 때문에 Object 배열을 활용해야 할 것이다.

따라서, 내가 Class를 생성한 이후 해당 클래스에 값과 원래 배열에서의 index를 동시에 저장한 이후 이를 활용하여 문제를 풀기로 하였다.

• 최근엔 기술의 발전으로 Memory의 한계가 많이 없어졌기 때문에, Object 배열에 대한 Tim Sort를 활용하도록 하자

코드

import java.util.*;

class Number implements Comparable<Number>{
	int data;   // 배열 원소 값 
	int index;  // 정렬 이전에 값이 존재하는 index
	
	public Number(int data, int index) {
		this.data = data;
		this.index = index;
	}
	
	@Override
	public int compareTo(Number n) {
        // 원소 배열은 배열의 값에 대해 비내림차순이므로 
        // <return this.X - n.X>로 구현
		return this.data - n.data;
	}
}

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

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.nextLine();
		Number[] numbers = new Number[N];
		
		String tmp = sc.nextLine();
		String[] split = tmp.split(" ");
		
		for(int i =0;i<N;i++) {
			numbers[i] = new Number(Integer.parseInt(split[i]),i);
		}
		
		Arrays.sort(numbers);
        // numbers는 Number로 구성된 배열이므로 Object 배열이다.
        // 따라서 Stable Sort이고, 자연스럽게 모든 조건을 만족시킨다.

		StringBuilder sb = new StringBuilder();
		for(int i =0;i<N;i++) {
           // 아래 참조
			numbers[numbers[i].index].data = i;
		}

		for(int i =0;i<N;i++) {
			sb.append(numbers[i].data+" ");
		}

		System.out.println(sb.toString());
	}

부가 설명

2 3 1 → 1 2 3으로 변환되었다고 생각하자.
이 때 <값, index> 쌍으로 표현한다면,
<2,0> <3,1> <1,2> → <1,2> <2,0> <3,1> 으로 정렬된 것이다.
<1,2>를 자세히 살펴보자.
1은 정렬 이후 0번째 index에 존재한다. 따라서 원래 배열에서 1이 있던 공간에는 0이 출력되어야 한다.(<1,2>이기 때문에 2번째 index, 사람 기준으로 3번째에 0이 출력됨)
우리는 원래 배열에서 1이 있던 공간을 Number class에서 index에 저장했었다.
즉, 정렬 이후 index(내가 출력하길 원하는 data)값을 원래 배열에서 존재하던 index번째에(Number Class에서 index에 저장한 data) 출력하고 싶은 것이다.

for(int i =0;i<N;i++) {
			numbers[numbers[i].index].data = i;
}

위 코드를 살펴보자.
numbers[i].index는 원래 배열에서의 index이다.
또한, i는 0 ~ N-1까지 for문을 수행하고, 정렬이 완료되었기 때문에 정렬 이후 index값을 의미한다.

따라서 위 문구는 아래 과정을 거쳐 답을 numbers의 data공간에 저장하는 것이다.

1. numbers[numbers[i].index]를 통해 원래 배열에서 존재하던 index 공간에 찾아간다.

2. 이 값은 정렬 이후 i번째에 출력되었다. 따라서, 1번에서 내가 찾아간 공간에는 i가 출력되어야 한다.

3. 더 이상 Sorting이 필요 없기 때문에 공간의 재활용을 위해 Number Class의 data값에 i를 저장한다.

4. 마지막으로 다시 0 ~ N-1을 차례대로 Search하며 3번에 저장됐던 data를 출력한다.

결과