[BOJ] 1015 - 수열 정렬

문제 링크

1015-수열 정렬

입력

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

출력

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

문제 풀이

Pair 클래스를 만들어서 사용
리스트에 pair를 집어넣는데 숫자와 그 숫자의 인덱스를 같이 집어넣어줌

Collections.sort를 이용해서 정렬
비내림차순이라면 value들끼리 비교해서 정렬
value가 같다면 idx가 앞서는 순으로 정렬

이후에 idx를 저장하는 리스트를 새로 만들어 결과 출력

Pair를 만들어 정렬한다는 생각만 들면 어렵지 않았다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Code1015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Pair> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            list.add(new Pair(i, Integer.parseInt(st.nextToken())));
        }

        Collections.sort(list, new Comparator<Pair>(){
            @Override
            public int compare(Pair o1, Pair o2) {
                if (o1.value < o2.value) {
                    return -1;
                } else if (o1.value > o2.value) {
                    return 1;
                } else {
                    if(o1.idx < o2.idx) return -1;
                    else return 1;
                }
            }
        });

        int[] p = new int[1001];
        for (int i = 0; i < n; i++) {
            p[list.get(i).idx] = i;
        }
        for (int i = 0; i < n; i++) {
            System.out.print(p[i] + " ");
        }

    }

    public static class Pair{
        int idx, value;

        Pair(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }
    }
}