백준 1083번 - 소트

문제

백준 1083번 - 소트

아이디어

• 사전순으로 가장 뒷서는 것이므로 최대한 큰 수가 앞에 배치되도록 해야 한다.
• 연속된 두 개의 원소와 최대 S번 교환이 가능하므로 앞에서 S번을 최대한 사용하면 큰 수가 앞에 오게 할 수 있을 것이다.
• 만약 앞에서 S번을 다 사용하지 않았다면 나머지 원소들에서 남은 S - a번을 사용할 수 있다.
• 이미 앞에 큰 수가 배치되어 있다면 굳이 교환하지 않을 수도 있다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_1083 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int s = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {

            int maxIdx = i;

            //현재 위치 이후에 S 범위 이내 가장 큰 값의 위치 찾기
            for (int j = i + 1; j <= i + s && j < n; j++) {
                if (arr[j] > arr[maxIdx]) {
                    maxIdx = j;
                }
            }

            //이미 큰 수가 앞에 있으면 S번 소모할 필요 없음
            if (maxIdx == i) continue;

            //최대 S 만큼 뒤에 있는 큰 수를 앞으로 가져오기
            for (int j = maxIdx; j > i; j--) {

                //swap
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;

                s--;
            }

            if (s <= 0) {
                break;
            }
        }

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}