[백준 1015] 수열 정렬

[문제 바로가기]👇

1015번: 수열 정렬

 

 

 

풀이

문제에서 3가지  배열 P, A, B가 주어지는데 주어진 세 가지 배열의 관계를 먼저 찾았다.

 

먼저 주어진 식을 보면

B[P[i]] = A[i]

수열 P의 값이 B배열의 인덱스가 된다는 걸 알 수 있다.

최종적으로 B배열이 오름차순(비내림차순)이 되어야 하기 때문에 A 배열을 오름차순으로 만들고 기존 A배열과 비교하면서 인덱스가 어떻게 바뀌었는지 찾으면 된다. 

 

이때 예제 2번, 3번처럼 중복된 값이 A배열에 있을 수도 있기 때문에 주의해야 한다.

그래서 P배열을 -1로 초기화를 해 i번째 인덱스가 -1이면 아직 P[i]의 값이 정해지지 않았다는 것을 의미하도록 했다.

 

그리고 기존 A 배열과 정렬된 A배열을 비교하며 정렬된 인덱스가 몇 번인지를 찾을 때 중복된 값의 경우 같은 인덱스만을 계속 찾을 수 있기 때문에 한 번 P배열에 저장된 값은 정렬된 A배열에서도 -1로 바꿔 이미 값을 찾았다는 것을 의미하도록 했다.

 

package M05_1;

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

public class B1015 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		
		int[] A = new int[N]; 
		int[] P = new int[N]; 
		int[] sort = new int[N]; 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken()); // A배열
			sort[i] = A[i]; // 정렬한 A배열을 저장할 배열
			P[i] = -1; // P배열
		}
		
		Arrays.sort(sort); // 정렬
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				// P배열의 i번째 자리가 정해지지 않았고 기존 A배열과 정렬된 A배열의 원소가 같으면
				if(P[i] == -1 && A[i] == sort[j]) {
					P[i] = j; // P[i]는 j인덱스가 되어야 함
					sort[j] = -1; // 사용됨 처리
				}
			}
		}
		
		for(int num : P) sb.append(num).append(" ");
		System.out.println(sb);
		br.close();
	}
	
}