[백준] 23883: 알고리즘 수업 - 선택 정렬 3 - JAVA

19 Oct 2023 in Algorithm on 자료 구조

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

풀이

선택정렬은 O(n^2)의 시간복잡도를 갖기때문에 그대로 구현하면 시간초과가 났다.

따라서 정렬이 되는 TreeMap을 이용했다.

TreeMap에 숫자와 처음 인덱스를 넣고 뒤에서 부터 꺼내면서 인덱스 교체가 필요할 경우 교체해주었다.

---

메모리: 122416KB

시간: 1564ms

언어: Java 11

코드

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

public class Main {

    static int[] arr;
    static int N, K, cnt, ans_a, ans_b;

    public static void main(String[] args) 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];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            map.put(arr[i], i);
        }

        cnt = 0;
        ans_a = 0;
        ans_b = 0;
        for (int i = N - 1; i >= 0; i--) {
            int m = map.pollLastEntry().getValue();
            if (i == m) {
                continue;
            }

            cnt++;
            boolean flag = swap(arr, map, i, m);

            if (flag) {
                break;
            }
        }

        if (ans_a == 0) {
            System.out.println(-1);
        } else {
            System.out.println(ans_a + " " + ans_b);
        }
    }

    private static boolean swap(int[] a, TreeMap<Integer, Integer> map, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        map.put(a[j], j);

        if (cnt == K) {
            ans_a = a[j];
            ans_b = a[i];
            return true;
        }

        return false;
    }

}