[Java] 백준 1083 소트 - 골드5

 

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

1083번: 소트

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int S = Integer.parseInt(br.readLine());

    ArrayList<Integer> list = new ArrayList<>();
    for (int i=0; i<N; i++)
      list.add(Integer.parseInt(st.nextToken()));
    //입력끝 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

    //자릿수마다 올 수 있는 최대값이 와야함
    for (int i =0; i<N; i++) {
      int maxIdx = -1;
      int max = -1;

      //범위 내 최댓값 찾기
      for (int j = i; j<N; j++) {
        if (max < list.get(j)) {
          max = list.get(j);
          maxIdx = j;
        }

        if (j == i+S)
          break;
      }

      //최댓값과 자리 교환
      S = S - (maxIdx - i);
      for (int j = maxIdx; j> i; j--)
        Collections.swap(list, j, j-1);

      if (S == 0)
        break;
    }

    String result = "";
    for (int i: list)
      result += ("" + i + " ");

    System.out.println(result.strip());
  }
}

• 높은 자릿수부터 낮은 자릿수로 가면서 올 수 있는 최댓값을 찾아서 교환하면 된다
• 교환가능한 범위가 S이기 때문에 자신의 인덱스 i부터 i+S까지 범위의 값들 중 최댓값을 찾아 나(i)와 교환한다
• S가 0이 되거나 각 자릿수에 올 수 있는 최댓값을 모두 찾으면 반복문이 끝난다