[백준] 1015_수열정렬 **

 

 

Sliver

 

문제

 

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

 

 

입력

 

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

 

 

출력

 

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

 

 

-> 요약하자면, 배열을 오름차순으로 정렬하였을 때의 해당 값의 인덱스를 구하는 문제이다. 

 

---

 

풀이

 

import java.util.*;

class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        // value, index
        List<Pair> list = new ArrayList<>();
        for(int i=0; i<N; i++){
            list.add(new Pair(arr[i], i));
        }

        // value기준 오름차 정렬
        list.sort((o1, o2) -> {
            return o1.value - o2.value;
        });
		
        // 원래 인덱스에 현재 오름차순 정렬된 인덱스 삽입
        int[] result = new int[N];
        for(int i=0; i<N; i++){
            result[list.get(i).index] = i;
        }

        for(int i=0; i<N; i++){
            sb.append(result[i] + " ");
        }
        System.out.println(sb);
        
        sc.close();
    }

    static class Pair{
        int value;
        int index;
        Pair(int value, int index){
            this.value = value;
            this.index = index;
        }
    }
}

 

 

// value기준 오름차 정렬
list.sort((o1, o2) -> {
	return o1.value - o2.value;
});
		
// 원래 인덱스에 현재 오름차순 정렬된 인덱스 삽입
int[] result = new int[N];
for(int i=0; i<N; i++){
	result[list.get(i).index] = i;
}

 

해결방법

1. 배열의 크기 N을 입력받아 N 크기의 int 배열 arr 을 생성하여 데이터를 저장한다. 

2. 배열의 원소(value) 와 현재 인덱스(index)를 쌍으로 저장할 수 있는 Pair 구조체를 생성하고, Pair 데이터를 저장하는 List를 생성한다. 

3. List를 원소 값 (value) 을 기준으로 오름차순 정렬한다. 

4. 정렬된 리스트를 사용하여 result 배열에 원래 인덱스에 value 기준 정렬된 현재 인덱스를 삽입한다. 

 

 

 

 

 

---

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