99클럽 코테 스터디 20일차 TIL [정렬]

 

- 오늘의 학습 키워드 : 정렬

[문제 이름 : 소트 (백준 1083, G4)]
문제 url : https://www.acmicpc.net/problem/1083

내가 작성한 코드는 아래와 같다.

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < input; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

        for (int i = 0; i < input && s > 0; i++) {
            // 교환할 수 있는 최대 범위 설정
            int maxIndex = i;
            for (int j = i + 1; j < input && j <= i + s; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            // 선택된 maxIndex의 값을 앞으로 가져옴
            for (int j = maxIndex; j > i; j--) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                s--;
            }
        }

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

풀이 과정 (풀이 시간 : 30분)

문제만 보면 언뜻 이해가 안될 수 있다. 쉽게 보면 사전 순으로 제일 늦게 오도록 연속된 두 수를 S번 변경할 수 있는 것이다. 문제의 예제만 가지고서는 이해가 잘 안 됐다. 그래서 다음과 같은 케이스를 생각해보았다.

N = 3, arr = 5 2 9로 이루어졌다고 할 때, S=1이면 5 9 2 가 되지만, S=2라면 9 5 2가 된다.

 

1. 교환할 수 있는 범위 내를 정한다.

for (int j = i + 1; j < input && j <= i + s; j++)

2. 범위 내에서 최대값을 찾는다.

3. 최대값만큼 배열 값을 이동시킨다.

내일은 SSAFY 코딩테스트에 대한 대비를 할 예정이다.