[Java] Boj 24051: 알고리즘 수업 - 삽입 정렬 1

문제

오늘도 서준이는 삽입 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 삽입 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 삽입 정렬 의사 코드는 다음과 같다.

insertion_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for i <- 2 to N {
        loc = i - 1;
        newItem = A[i];

        # 이 지점에서 A[1..i-1]은 이미 정렬되어 있는 상태
        while (1 <= loc and newItem < A[loc]) {
            A[loc + 1] <- A[loc];
            loc--;
        }
        if (loc + 1 != i) then A[loc + 1] = newItem;
    }
}

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 저장 횟수 K(1 ≤ K ≤ N2)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

출력

K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

예제 입력 1 

5 7
4 5 1 3 2

예제 출력 1 

5

4 5 1 3 2 -> 4 5 5 3 2 -> 4 4 5 3 2 -> 1 4 5 3 2 -> 1 4 5 5 2 -> 1 4 4 5 2 -> 1 3 4 5 2 -> 1 3 4 5 5 -> 1 3 4 4 5 -> 1 3 3 4 5 -> 1 2 3 4 5. 총 10회 저장이 발생하고 일곱 번째 저장되는 수는 5이다.

예제 입력 2 

5 11
4 5 1 3 2

예제 출력 2 

-1

저장 횟수 10이 K 보다 작으므로 -1을 출력한다.

---

풀이

기초적 정렬 문제 시리즈에서 삽입 정렬 문제이다.

삽입 정렬이란 적절한 위치에 원소를 삽입하며 정렬해나가는 방법으로, 배열에서 1 ~ i까지의 원소가 정렬되어 있을 때 arr[i + 1] 원소를 1 ~ i의 적절한 위치에 삽입하는 방식이다.

이 결과로 1 ~ i +1까지의 원소들은 정렬되고, 다음으로 arr[i + 2] 원소를 같은 방법으로 삽입 정렬하며 정렬해 나간다.

 

이미 배열이 정렬되어 있는 상태에서는 배열 크기만큼 탐색하므로 최선의 경우에 n의 시간 복잡도를 가지고

역순으로 배열이 정렬되어 있는 최악의 경우에는 n^2만큼의 시간 복잡도를 가지게 된다.

 

문제에서 주어진 의사 코드대로 삽입 정렬을 구현하면 되는데, 값의 저장이 2회 일어나는 것에 유의해야 한다.

이것에 유의하여 삽입 정렬을 구현하면 완료.

 

이렇게 기본적인 정렬 방식으로 생각할 수 있는 버블 정렬, 삽입 정렬, 선택 정렬에 대하여 알아보았다.

위에서 언급한 정렬 방법들의 시간 복잡도는 n^2인데 이것은 정렬 속도가 느린 편에 속하지만, 정렬 방식에 대한 이해가 쉽고 간단하게 구현할 수 있다는 장점이 있다.

이외의 퀵 정렬, 쉘 정렬은 정렬 방식과 구현이 조금 어렵지만, 위에서 언급한 방식보다 시간 복잡도 측면에서 이점이 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static int k;
    public static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int size = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        int[] arr = new int[size + 1];
        for (int i = 1; i <= size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        insertion_sort(arr);
        if (cnt < k) {
            System.out.println(-1);
        }
    }
 
    public static void insertion_sort(int[] arr) {
        for (int i = 2; i < arr.length; i++) {
            int loc = i - 1;
            int newItem = arr[i];
            while (1 <= loc && newItem < arr[loc]) {
                arr[loc + 1] = arr[loc];
                cnt++;
                if (cnt == k) {
                    System.out.println(arr[loc]);
                    return;
                }
                loc--;
            }
            if (loc + 1 != i) {
                arr[loc + 1] = newItem;
                cnt++;
                if (cnt == k) {
                    System.out.println(newItem);
                    return;
                }
            }
        }
    }
}