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

 문제 : boj23882

---

 

필요 알고리즘 개념

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

※ 제 코드에서 왜 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) 인 경우이다. 그럼 이 때 교환을 진행한 후, 현재 배열을 그대로 출력해주면 될 것이다. 내 경우엔 위 로직을 추가하기 위해 아래의 코드를 추가해줬다.

if (++swapCnt == K) {
    StringBuilder sb = new StringBuilder();
    for (int j = 1; j <= N; j++) {
        sb.append(A[j]).append(' ');
    }
    System.out.println(sb);
    return;
}

 

 

---

 

코드 : github

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

public class Main {
    private static int N, K;

    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) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = 1; j <= N; j++) {
                        sb.append(A[j]).append(' ');
                    }
                    System.out.println(sb);
                    return;
                }
            }
        }
        System.out.println(-1);
    }

    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);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}