알고리즘

[BOJ-1015] 수열 정렬 - JAVA 풀이

sppl24 2024. 11. 3. 15:59
반응형

수열 정렬

문제

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를 출력한다.

입출력

입출력 예

아이디어

  • 문제가 한번에 잘 이해가 되진 않았다
  • B가 비내림차순으로 나올때의 인덱스를 구하면 되겠다
  • 결국은 정렬문제인데 왜 오름차순이 아니라 비내림차순인가 싶었는데 조금 다른 개념이었다
    • (비내림차순은 같은값인 경우에도 순서 유지)

JAVA 풀이

package boj.sample;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj1015 {
    static StringBuilder sb = new StringBuilder();
    static BufferedReader br;
    static int N;
    static int[] P;
    static BIdx[] B;

    public static class BIdx implements Comparable<BIdx> {
        public int n, idx;
        @Override
        public int compareTo(BIdx b) {
            return n - b.n;
        }
    }

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

        B = new BIdx[N];
        P = new int[N];
        for (int i = 0; i < N; i++) {
            B[i] = new BIdx();
            B[i].n = Integer.parseInt(st.nextToken());
            B[i].idx = i;
        }
        Arrays.sort(B);
        for (int i = 0; i < N; i++) {
            P[B[i].idx] = i;
        }
        for (int i = 0; i < N; i++) {
            sb.append(P[i]).append(' ');
        }
        System.out.println(sb.toString());
    }
}
반응형