[Java] Boj 23881: 알고리즘 수업 - 선택 정렬 1

문제

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

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

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

selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for last <- N downto 2 {
        A[1..last]중 가장 큰 수 A[i]를 찾는다
        if (last != i) then A[last] <-> A[i]  # last와 i가 서로 다르면 A[last]와 A[i]를 교환
    }
}

입력

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

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

출력

K 번째 교환되는 두 개의 수를 작은 수부터 한 줄에 출력한다. 교환 횟수가 K 보다 작으면 -1을 출력한다.

예제 입력 1

5 2
3 1 2 5 4

예제 출력 1 

2 3

3 1 2 5 4 (4와 5가 교환됨) -> 3 1 2 4 5 (A[1..4]에서 4가 가장 크므로 교환이 발생하지 않음) -> 3 1 2 4 5 (2와 3이 교환됨) -> 2 1 3 4 5 (1과 2가 교환됨) -> 1 2 3 4 5. 총 3회 교환이 발생하고 두 번째 교환은 2와 3이다.

예제 입력 2 

5 4
3 1 2 5 4

예제 출력 2 

-1

교환 횟수 3이 K 보다 작으므로 -1을 출력한다.

---

풀이

선택 정렬이란 현재 정렬할 데이터를 오름차순 순서대로 원소를 재배치 하면서 데이터를 정렬하는 방법이다.

n개의 원소 중 가장 작은 원소를 찾고, 그 원소와 arr[0]의 원소를 교환한다.

이후 남아있는 n-1개의 원소들 중 가장 작은 원소를 찾고, 그 원소와 arr[1]의 원소를 교환한다. (배열의 최솟값은 이미 arr[0]에 위치)

이 방식을 n-1회동안 반복하여 선택 정렬을 완료할 수 있다.

1번째에서 원소를 n-1회 비교하여 최솟값을 찾고, 2번째에서 원소를 n-2회, 3번째에서는 n-3회, ... , i번째에서는 n-i회의 비교를 통해 최솟값을 찾아낸다.

이렇게 최솟값을 n번의 루프동안 찾아내므로 시간 복잡도는 n^2가 된다. 

 

알고리즘을 시작하면 가장 처음 접하는게 정렬과 탐색이라 생각하는데, 앞선 포스팅에서 살펴본 버블 정렬에 이어 또 다른 정렬 방식인 선택 정렬에 대한 간단한 문제이다.

문제에서는 가장 큰 인덱스부터 정렬해 나가는데, 앞서 설명한 선택 정렬의 방식을 배열 끝부터 적용해 나가면 된다.

0 ~ i 범위에서 최댓값을 선택해 교환할 때마다 횟수를 count하고, 그 count를 입력받은 k와 비교하여 조건에 맞게 결과를 출력하면 된다.

이전에 해결하였던 버블 정렬 문제와 상당히 유사한 문제. 

코드

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];
        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        selection_sort(arr);
        if (cnt < k) {
            System.out.println(-1);
        }
    }
 
    public static void selection_sort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            int max = arr[i]; int index = i;
            for (int j = i - 1; j >= 0; j--) {
                if (max < arr[j]) { // 가장 큰 값 찾기
                    max = arr[j];
                    index = j;
                }
            }
            if (max != arr[i]) {
                int tmp1 = arr[i];
                arr[i] = max;
                arr[index] = tmp1;
                cnt++;
                if (cnt == k) {
                    System.out.print(arr[index] + " " + max);
                    return;
                }
            }
        }
    }
}