[Java]백준_23881 : 알고리즘 수업 - 선택 정렬 1

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

 

 

 

 

문제 분석

선택 정렬을 직접 구현하는 문제이다.

 

선택 정렬의 가장 기본적인 원리는 가장 작은 데이터를 선택해서 앞으로 보내는 알고리즘이다.

한 바퀴 돌면서 가장 작은 데이터를 찾아서 맨 앞 데이터와 교환하고, 그 다음 작은 데이터를 찾아서 그 다음 위치와 교환하는 식으로 동작한다.

배열 [5, 3, 8, 4, 2]로 동작 원리를 살펴보겠다.

 

 

<1회전>

전체 [5, 3, 8, 4, 2] 중 가장 작은 값: 2 -> 첫 번째 값 5와 교환

=> 결과 : [2, 3, 8, 4, 5]

 

<2회전>

남은 부분 [3, 8, 4, 5]에서 가장 작은 값: 3 -> 그대로 유지

=> 결과 : [2, 3, 8, 4, 5]

 

<3회전>

남은 부분 [8, 4, 5]에서 가장 작은 값: 4 -> 8과 교환

=> 결과 : [2, 3, 4, 8, 5]

 

<4회전>

남은 부분 [8, 5]에서 가장 작은 값: 5 -> 8과 교환

=> 결과 : [2, 3, 4, 5, 8]

 

이런 식으로 선택 정렬은 가장 작은 값을 선택해서 앞으로 보내는 알고리즘이다.

 

하지만, 해당 문제는 전체 배열 중 큰 수를 뒤로 보내는 방법이니 주의하자.

 

 

소스 코드 (⭕)

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

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

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int maxIndex = 0;
            int maxValue = 0;
            for (int j = 0; j < n - i; j++) {
                if (maxValue < arr[j]) {
                    maxValue = arr[j];
                    maxIndex = j;
                }
            }

            if (maxIndex != n - i - 1) {
                int temp = arr[n - i - 1];
                arr[n - i - 1] = maxValue;
                arr[maxIndex] = temp;
                cnt++;

                if (cnt == k) {
                    System.out.println(temp + " " + maxValue);
                    return;
                }
            }
        }
        System.out.println(-1);
    }
}

 

코드 분석

1. 각 값들을 입력 받고, swap 횟수를 카운트 할 변수 cnt를 선언한다.

 

2. 선택 정렬은 총 n개의 데이터를 정렬하는데, 오른쪽 끝부터 하나씩 정렬이 확정되니까 i가 커질수록 정렬 안 해도 되는 구간이 늘어난다는 점을 이용하여 바깥 for문은 n번, 안쪽 for문은 n- i 번으로 조건을 설정해준다.

 

3. 최댓값과 최댓값이 있는 index 위치를 저장할 변수를 선언하고, 안쪽 for문을 통해 배열의 최댓값을 찾는다.

 

4. 만약, 최댓값의 자리가 (정렬이 끝난 위치 제외) 맨 뒤가 아니라면 swap을 해주고 swap 횟수를 카운트 해준다. 최댓값이 맨 뒤에 있으면 swap할 필요가 없기 때문에 조건문을 써주는 것이다.

 

5. 만약, cnt의 값이 k값과 동일하다면, 바로 위에서 swap한 두 수를 출력하고 프로그램을 종료한다. 종료되지 않고 반복문을 빠져나왔으면, swap 횟수가 k보다 작은거니까 -1을 출력한다. 

 

 

 

end

버블 정렬에 비하면 동작 메커니즘이 쉬워서 for문 조건식과 함께 문제를 쉽게 풀 수 있었다.