BOJ_1083 소트 Gold.5

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

• 사전순이라는 의미는 배열의 원소를 기준으로 내림차순으로 정리하면 가장 큰 값이 되기 때문에 사전순으로 뒷선다고 표현할 수 있다

잘못된 방법은 배열의 시작부터 차례대로 S번 이내로 해당 인덱스의 값이 다음 인덱스의 값보다 작으면 바꿔주려고 하면 틀리게 된다

올바른 방법은 S번 이내의 원소 중, 현재 인덱스의 값보다 큰 값중, 가장 큰 값과 교환을 해야 한다. 그 이후, S값을 움직인 거리만큼 감소시켜주면 된다.

그 이유는 앞자리의 값이 가장 클수록 사전순으로 가장 뒷서기 때문이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static class Status implements Comparable<Status> {
        int value;
        int index;

        public Status(int value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(Status o) {
            return Integer.compare(this.value, o.value);
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 크키가 N인 배열 A
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); // 배열에 있는 모든 수는 서로 다름
        int S = Integer.parseInt(br.readLine()); // S
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Status> pq;


        for (int i = 0; i < N; i++) {
            pq = new PriorityQueue<>(Comparator.reverseOrder());
            int cnt = 0;
            for (int j = i + 1; j < N; j++) {
                if(cnt >= S) break;

                if (arr[j] > arr[i]) {
                    pq.add(new Status(arr[j], j));
                }
                cnt++;
            }

            if (!pq.isEmpty()) {
                Status status = pq.poll();
                changeValue(arr, status, i);
                S -= (status.index - i);
            }
        }

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

    private static void changeValue(int[] arr, Status status, int index) {
        for (int i = status.index; i > index; i--) {
            int value = arr[i];
            arr[i] = arr[i - 1];
            arr[i - 1] = value;
        }
    }
}