[백준] 1083번. 소트(JAVA)

문제

https://www.acmicpc.net/problem/1083

---

풀이(25분)

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

public class Main {

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

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

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

        ArrayList<Integer> arr = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(st.nextToken()));
        }

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

        int moveCnt = 0;
        int changeIdx = 0;
        while (moveCnt < S && changeIdx < N - 1) {
            int maxNum = arr.get(changeIdx);
            int maxIdx = -1;

            int idx = changeIdx + 1;
            int count = 1;
            while (moveCnt + count <= S && idx < N) {
                int num = arr.get(idx);
                if (num > maxNum) {
                    maxNum = num;
                    maxIdx = idx;
                }
                count++;
                idx++;
            }

            if (maxIdx != -1) {
                arr.remove(maxIdx);
                arr.add(changeIdx, maxNum);
                moveCnt += maxIdx - changeIdx;
            }
            changeIdx++;
        }

        StringBuilder sb = new StringBuilder();
        for (int i : arr) {
            sb.append(i).append(' ');
        }
        System.out.println(sb);
    }
}

---

문제 풀이 전략

 

생각해 보면 되게 간단한 문제이다.

 

문제에서 제시된 예제를 보자.

10
19 20 17 18 15 16 13 14 11 12
5

10개의 수 19, 20,... 을 5번 바꾼 것 중 사전순으로 제일 뒤에 있는 것을 찾으라는 뜻이다.

 

사전순으로 제일 뒤에 가게 되려면 큰 것이 제일 앞에 오는 게 우선이다. 그 뒤에 값이 어떻든 무조건 큰 수가 오는 게 우선이다.

그 말은 하나를 바꾼 뒤가 어쩌고 저쩌고 상관 없이, 일단 제일 앞에서부터 가능한 큰 수를 놓자!라는 것이다.

19를 바꿀 수 있는 후보로는 20(1), 17(2), 18(3), 15(4), 16(5) 이다. 그럼 당연히 20과 바꿔야 한다!

 

즉, 한번 바꾼 후에는 20, 19, 17, ... 이 된다.

이제 s = 4로 줄었을 것이고, 19의 후보군에는 여전히 16(4)이 위치하게 된다. 여기서 16(5) -> 16(4)가 되었음을 생각하자.

바꿀 이유가 없으니 패스한다. 이런 식으로 앞에서부터 큰 수를 맞춰가면 된다!

 

또한 N은 50까지인 반면 S의 최댓값은 매우 크기 때문에 S가 N의 길이보다 크거나 같다면 최댓값을 가져와서 변경해 주면 된다!