[ 백준 23881번 문제 ] 알고리즘 수업 - 선택 정렬 1

이번 글에서는 백준 23881번 문제를 통해 선택 정렬 동작 원리를 확인, 활용해 보겠습니다.
선택 정렬에 대한 정리는 다음 게시글에 있습니다.

https://p-coding.tistory.com/100

[ 알고리즘 ] 선택 정렬

 

문제 핵심

• 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다.
• 이 과정에서 K 번째 교환이 이루어질 때 교환되는 두 수를 반환하며, K번 미만일 때 특정 결과인 -1을 반환한다.
• N : 배열의 길이
• K : 목표 교환 횟수

---

풀이과정

먼저 BufferedReader를 통해 값을 받습니다. Scanner를 사용할 수 있으나 하나씩 처리하는 방식은 시간 제한에 걸릴 수 있으므로 Buffer를 활용한 클래스를 사용하는 것을 추천드립니다.

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        swapCount = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

• N과 K(swapCount) 값을 저장
• 배열의 원소들을 받고, tokenizer를 통해 받은 값을 분리하여 저장

        int count = -1;
        if (arr.length < 2) {
            System.out.println(count);
        }

        int maxIndex;
        for (int i = arr.length - 1; i > 0; i--) {
            maxIndex = i;

            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            if (maxIndex != i) {
                count++;
                if (swapCount == (count + 1)) {
                    System.out.println(arr[i] + " " + arr[maxIndex]);
                    return;
                }
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[i];
                arr[i] = temp;

            }
        }

        System.out.println(-1);

• count는 -1로 시작 ( 0으로 시작할 때와 값이 1차이 )
• 교환이 이루어지지 않는다면 -1 출력
• 기준점을 마지막 원소로 잡고 maxIndex에 저장한다
• j ( 마지막 원소 - 1 ) 부터 1씩 감소하여 비교 후 높은 값이 있다면 위치를 기억해 둔다.
• maxIndex와 i 값이 다르다면 위치 변경과 변경 횟수를 1 증가한다.
• 반복하며 K(교환 횟수)에 도달했는지 체크한다.

전체 코드

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

public class Main {
    private static int[] arr;
    private static int swapCount;

    public static void main(String[] args) {
        try {
            prepare();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }

        selection_sort();

    }

    private static void prepare() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        swapCount = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

    }

    private static void selection_sort() {
        int count = -1;
        if (arr.length < 2) {
            System.out.println(count);
        }

        int maxIndex;
        for (int i = arr.length - 1; i > 0; i--) {
            maxIndex = i;

            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            if (maxIndex != i) {
                count++;
                if (swapCount == (count + 1)) {
                    System.out.println(arr[i] + " " + arr[maxIndex]);
                    return;
                }
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[i];
                arr[i] = temp;

            }
        }

        System.out.println(-1);

    }
}

 

선택 정렬 활용의 기초단계로 시험해보기 좋은 문제이다.