[자바] 백준 23881 - 알고리즘 수업 - 선택 정렬 1 (java)

 문제 : boj23881

---

 

필요 알고리즘 개념

•  시뮬레이션
  • 문제 자체가 풀이에 해당하고 문제 그대로 구현해주면 되므로 시뮬레이션이라 볼 수 있다. 딱히 이걸 알아야 풀 수 있는건 아니다.
• 정렬
  
  • 정렬이 뭘 하는건지 알고 있어야 한다.역시 딱히 이걸 알아야 풀 수 있는건 아니다. 문제 자체가 풀이에 해당하므로!

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  문제 자체가 풀이에 해당하기 떄문에 별도로 말할건 없을 것 같다. 그래도 설명을 해보자면, 우선 문제에 작성되어 있는 의사코드를 그대로 자바코드로 구현하면 아래와 같다. 정확히 수도코드대로 구현했다.

private void selectionSort(int[] A) {   // A[1..N]을 오름차순 정렬한다.
    for (int last = n; last >= 2; last--) {
        // A[1..last]중 가장 큰 수 A[i]를 찾는다
        int max = Integer.MIN_VALUE;
        int i = 0;
        for (int idx = 1; idx <= last; idx++) {
            if (max < A[idx]) {
                max = A[idx];
                i = idx;
            }
        }

        // last와 i가 서로 다르면 A[last]와 A[i]를 교환
        if (last != i) {
            int tmp = A[last];
            A[last] = A[i];
            A[i] = tmp;
        }
    }
}

 

 

  이 문제는 삽입 정렬을 구현하는건 아니고, K번째 교환의 값들을 알아야 하니 위 코드에서 그 부분만 추가로 넣어주면 된다. if (last != i) 인 경우가 교환이 발생한 경우이다. 따라서 교환이 발생한 횟수를 세다가 K와 같아질 경우 해당 교환결과를 출력해주면 된다. 만약 끝까지 다 진행해봐도 교환횟수가 K보다 작다면 -1을 출력해주면 된다.

 

  위 코드의 경우 O(N^2)의 시간복잡도로, N이 최대 10000이므로 문제없이 통과 가능하다. K번째 값을 출력하는 로직은 이하 첨부한 코드를 참고해보자.

 

---

 

코드 : github

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

public class Main {
    private static int N, K, kth1=-1, kth2;

    private void selectionSort(int[] A) {   // A[1..N]을 오름차순 정렬한다.
        int swapCnt = 0;
        for (int last = N; last >= 2; last--) {
            // A[1..last]중 가장 큰 수 A[i]를 찾는다
            int max = Integer.MIN_VALUE;
            int i = 0;
            for (int idx = 1; idx <= last; idx++) {
                if (max < A[idx]) {
                    max = A[idx];
                    i = idx;
                }
            }

            // last와 i가 서로 다르면 A[last]와 A[i]를 교환
            if (last != i) {
                int tmp = A[last];
                A[last] = A[i];
                A[i] = tmp;

                if (++swapCnt == K) {
                    kth1 = A[i];
                    kth2 = A[last];
                    return;
                }
            }
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N +1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        selectionSort(arr);
        System.out.println(kth1==-1?-1:(kth1 + " " + kth2));
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}