[백준 1083] 소트 (JAVA)

문제

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

풀이

1번째 자리부터 최대한 큰 수를 넣어야 하므로 1번째부터 시작하여 최대한 넣을 수 있는 큰 수를 찾아서 넣습니다.

배열 : [3, 5, 1, 2, 4]
S : 2

• 첫 번째 자리에 들어갈 수 있는 숫자는 3, 5, 1입니다. 가장 큰 숫자인 5를 넣고 첫 번째 자리와 5의 거리만큼 이동거리를 카운트합니다.
  
  
  
  
  
  

• 3과 5를 바꾸면서 교환을 1번 사용했기 때문에 두 번째 자리에 들어갈 수 있는 숫자는 3, 1입니다. 1이 3보다 작으므로 바꿀 필요가 없습니다.
  
  
  
  
  
  

• 세 번째 자리에는 들어갈 수 있는 숫자는 1, 2입니다. 가장 큰 숫자인 2를 세 번째 자리에 넣습니다.
  
  
  
  
  
  

모든 교환을 사용했으므로 정답은 [5, 3, 2, 1, 4]입니다.

코드

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

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, changeIdx = 0;
        while (moveCnt < S && changeIdx < N - 1) {
            int maxNum = arr.get(changeIdx), maxIdx = -1;

            int idx = changeIdx + 1, 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);
        br.close();
    }
}