백준 1083

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

1083번: 소트

문제 이해

해당 문제는 소팅하는 단순한 문제이지만 정해진 횟수만 반복해서 가장 큰수를 찾아야 한다.

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

 

풀이

처음 부타 마지막까지 반복하면서 가장 큰수를 찾고 해당 수를 앞으로 넘기는 방식으로 풀이를 진행한다.

단 여기서 변경할 수 있는 범위는 S에 다라서 정해진다.

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

public class test40 {
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        arr = new int[N];

        String[] str = br.readLine().split(" ");

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }

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

        for (int i = 0; i < N - 1; i++) {
            //변경 횟수 끝나면 끝
            if (S == 0) {
                break;
            }

            //최대값 위치 저장
            int max = arr[i];
            int index = i;

            //변경 가느안 위치까지 반복
            for (int j = i; j <= i + S; j++) {
                //범위를 넘어가면 끝
                if (j >= N) break;

                //범위를 넘지 않는 선에서 최대값 선택
                if (arr[j] > max) {
                    max = arr[j];
                    index = j;
                }
            }
            
            //index가 i랑 같아질때 까지
            //소팅
            while (index > i) {
                sort(index, index - 1);
                index--;
                S--;
            }
        }

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

    static void sort(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}