👨‍💻 문제

크기가 N인 배열 A가 있다.

배열에 있는 모든 수는 서로 다르다.

이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다.

그리고, 교환은 많아봐야 S번 할 수 있다.

이 때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

⌨️ 입력

첫째 줄에 N이 주어진다.
N은 50보다 작거나 같은 자연수이다.

둘째 줄에는 각 원소가 차례대로 주어진다.
이 값은 1000000보다 작거나 같은 자연수이다.

마지막 줄에는 S가 주어진다.
S는 1000000보다 작거나 같은 음이 아닌 정수이다.

🖨️ 출력

첫째 줄에 문제의 정답을 출력한다.

📖 예제

입력

5
3 5 1 2 4
2

출력

20 10 30 40 50 60 70

---

✍️ 풀이

교환 횟수가 제한된 버블 정렬 문제이다.

전체적인 알고리즘 흐름을 먼저 설명하겠다.

인덱스 0에서부터 끝까지 만들 수 있는 가장 큰 값을 정해나간다.

오른쪽 (현재 인덱스보다 큰 인덱스) 에 존재하는 가장 큰 값을 오큰수라 칭하겠다.
오큰수가 존재하고, 이를 현재 인덱스까지 교환할 수 있다면 교환한다.

해당 문제의 교환은 연속된 두 수의 교환이다.
현재 인덱스와 오큰수 인덱스의 차이만큼의 교환 횟수를 소모하여 연쇄적으로 교환할 수 있다.

📌 아래의 케이스는 다양한 경우에 대응하는 케이스이다.

Case 1 :

배열 : 4 0 2 1 3 5
최대 교환 횟수 : 7

인덱스 0 값 선택

📌 정상적인 교환이 이루어진 경우

4 0 2 1 3 5
오큰수 : 5
오큰수 거리 : 5
잔여 교환 : 7

5 4 0 2 1 3
잔여 교환 : 2

인덱스 1 값 선택

📌 오큰수가 없는 경우

5 4 0 2 1 3
오큰수 : 없음
잔여 교환 : 2

👉 본인이 가장 큰 수이므로 교환하지 않음

인덱스 2 값 선택

📌 오큰수를 교환해낼 수 없는 경우 ( 오큰수 거리 > 잔여 교환 )
5 4 0 2 1 3
오큰수 : 3
오큰수 거리 : 3
잔여 교환 : 2

👉 그 다음으로 큰 수를 찾아내어 교환을 시도한다.
5 4 0 2 1 3
2nd 오큰수 : 2
오큰수 거리 : 1
잔여 교환 : 2

5 4 2 0 1 3
잔여 교환 : 1

인덱스 3 값 선택

📌 잔여 교환이 0이 되어 더 이상 진행할 수 없게 되는 경우
5 4 2 0 1 3
오큰수 : 3
오큰수 거리 : 2
잔여 교환 : 1

5 4 2 0 1 3
2nd 오큰수 : 1
오큰수 거리 : 1
잔여 교환 : 1

5 4 2 1 0 3
잔여 교환 : 0

👉 교환을 종료하고 결괏값 5 4 2 1 0 3을 출력한다.

📌 이 외에 정렬이 끝났음에도 교환 횟수가 남아있는 경우 :
교환은 많아봐야 S번 할 수 있다고 명시되어 있기 때문에 남는 것은 무방하다.
본인은 교환이 남으면 안 되는 줄 알고 추가 알고리즘을 작성하여 틀렸었다.

---

✍️ 코드 풀이

⌨️ 데이터 입력

    static int N, S;
    static int[] Arr;
    
    public static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        Arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            Arr[i] = Integer.parseInt(st.nextToken());
        }

        S = Integer.parseInt(br.readLine());
    }

---

🔄 정렬 알고리즘

    public static void sort(){
        Comparator<int[]> comp = new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        };

        for(int i=0; i<N && S>0; i++){
            PriorityQueue<int[]> num = new PriorityQueue<>(comp); // [숫자,인덱스]
            for(int j=i; j<N; j++){
                num.add(new int[]{Arr[j],j});
            }

            while(!num.isEmpty()){
                int targetIndex = num.poll()[1];
                int swapCnt = targetIndex - i;
                if(S >= swapCnt){
                    if(swapCnt>0){
                        pull(i, targetIndex);
                        S -= swapCnt;
                    }
                    break;
                }
            }
        }
    }

📌 int 배열 우선순위 큐

        Comparator<int[]> comp = new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        }; 

            PriorityQueue<int[]> num = new PriorityQueue<>(comp); // [숫자,인덱스]
            for(int j=i; j<N; j++){
                num.add(new int[]{Arr[j],j});
            }     

숫자들의 순서 저장 및 탐색을 효율적으로 하기 위해 사용하였다.

배열은 {숫자, 인덱스} 형태로 구성되며
우선순위 큐는 숫자 기준 내림차순으로 정렬한다.

i : 값을 정할 인덱스
이미 정해진 값들은 큐에 넣을 필요가 없다.

---

📌 교환

			while(!num.isEmpty()){
                int targetIndex = num.poll()[1];
                int swapCnt = targetIndex - i;
                if(S >= swapCnt){
                    if(swapCnt>0){
                        pull(i, targetIndex);
                        S -= swapCnt;
                    }
                    break;
                }
            }

우선순위 큐에서 가장 큰 값을 우선적으로 불러온다.
targetIndex : 오큰수 인덱스
swapCnt : 오큰수 거리
i : 값을 정할 인덱스
S : 잔여 교환 횟수

교환할 수 있다면 교환하고 아니라면 다음으로 큰 값을 불러와 교환할 수 있을 때까지 반복한다.
이 과정에서 현재 인덱스의 값을 호출한다면 swapCnt는 0이 되어 break하고 다음 인덱스를 탐색하게 된다.

pull() 메소드는 아래와 같다.

    public static void pull(int to, int from){
        int tmp = Arr[from];
        for(int i=from; i>to; i--){
            Arr[i] = Arr[i-1];
        }
        Arr[to] = tmp;
    }

        for(int i=0; i<N && S>0; i++){...}

교환은 인덱스 0부터 N-1까지 값을 정했거나 ( 모두 정렬되었거나 )
교환 횟수가 남아있지 않을 때까지 진행한다.

---

📄 전체 소스코드

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

public class Main {

    static int N, S;
    static int[] Arr;

    public static void main(String[] args) throws IOException{
        input();
        sort();
        print();
    }

    public static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        Arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            Arr[i] = Integer.parseInt(st.nextToken());
        }

        S = Integer.parseInt(br.readLine());
    }

    public static void sort(){
        Comparator<int[]> comp = new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        };

        for(int i=0; i<N && S>0; i++){
            PriorityQueue<int[]> num = new PriorityQueue<>(comp); // [숫자,인덱스]
            for(int j=i; j<N; j++){
                num.add(new int[]{Arr[j],j});
            }

            while(!num.isEmpty()){
                int targetIndex = num.poll()[1];
                int swapCnt = targetIndex - i;
                if(S >= swapCnt){
                    if(swapCnt>0){
                        pull(i, targetIndex);
                        S -= swapCnt;
                    }
                    break;
                }
            }
        }
    }

    public static void pull(int to, int from){
        int tmp = Arr[from];
        for(int i=from; i>to; i--){
            Arr[i] = Arr[i-1];
        }
        Arr[to] = tmp;
    }

    public static void print(){
        StringBuilder sb = new StringBuilder();
        for(int e : Arr){
            sb.append(e).append(' ');
        }
        System.out.println(sb);
    }
}