[BOJ] 23883 - 알고리즘 수업 선택 정렬 3

문제

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

링크를 확인해보세요.

www.acmicpc.net

문제 정리

시간 제한	메모리 제한	정답 비율
3 초	512 MB	29.8%

요약

• 선택 정렬에서 K 번째 교환되는 두 수를 구하시오.

입력 조건

• N (배열 크기) : 5 ~ 500,000
  • 배열의 원소는 서로 다른 값입니다.
• K (교환 횟수) : 1 ~ A

출력

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

---

문제 풀이

배열의 크기를 고려 했을, 단순히 선택 정렬을 구현하여 K 번째 교환 되는 두 수를 찾는 방식은 최악의 경우 시간 복잡도가 O({{pow:10|10}})이 되어 시간 초과 됩니다.

선택 정렬 의사 코드 보면 다음과 같습니다.

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

여기서 핵심은 반복 마다 최댓값을 찾는 과정을 가집니다. 해당 탐색 과정을 O(logN)으로 개선할 수 있으면, 전체 알고리즘의 시간을 O(NlogN)로 줄여서 문제를 해결할 수 있습니다.

아이디어

• 정렬을 통하여 최종 상태를 미리 계산합니다. (O(NlogN))
• 값 -> 인덱스 매핑을 통하여, 각 값의 현재 위치를 O(1)에 조회할 수 있습니다.
• 현재 상태와 정렬 상태가 다르면 교환을 수행하면서 해를 찾아갑니다.

결과적으로 최댓값을 매번 탐색하는 대신 “정렬된 결과 + 인덱스 매핑”을 활용하여 선택 정렬 과정을 시뮬레이션함으로써 전체 시간 복잡도를 O(NlogN)로 줄 일 수 있습니다.

---

풀이 코드

import java.util.*;
import java.lang.*;
import java.io.*;


class Main {

    void solve() throws Exception {
        // 변수 초기화
        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[] A = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        // 현재 숫자의 index를 저장하기 위한 맵.
        HashMap<Integer, Integer> numIdx = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            numIdx.put(A[i], i);
        }

        // 정렬 통하여 최댓값 순서 찾기.
        int[] sortedA = Arrays.stream(A)
                .sorted().toArray();

        for (int i = A.length - 1; i >= 0; i--) {
            // 원본과 정렬된 데이터 값이 동일하지 않으므로 교환 발생.
            if (A[i] != sortedA[i]) {
                K -= 1;

                if (K == 0) {
                    System.out.println(A[i] + " " + sortedA[i]);
                    break;
                }

                // A[i]가 실제로 이동할 위치.
                int loc = numIdx.get(sortedA[i]);

                A[loc] = A[i];  // 값 이동

                // 인덱스 업데이트
                numIdx.put(A[i], loc);
            }
        }

        if (K != 0) {
            System.out.println(-1);
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}