[JAVA]백준 24060번 알고리즘 수업 - 병합 정렬 1

📌문제 링크

---

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

📌문제 설명

---

문제에 써 있는 그대로 구현하면 되는 문제입니다. 마지막 merge과정의 저장 횟수를 잘 세서 K와 비교하는 로직만 잘 구현하면 됩니다.

📌코드

---

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] A = new int[500001];
    static int N, K, cnt = 0, answer = -1;
    static int[] temp = new int[500001];

    public static void main(String[] args) throws Exception{
        input(); // 입력 함수 호출
        solve(); // 문제 해결 함수 호출
    }

    public static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 첫 번째 입력: N
        K = Integer.parseInt(st.nextToken()); // 두 번째 입력: K
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken()); // 배열 A에 숫자 입력
        }
        br.close(); // 입력 스트림 닫기
    }

    public static void merge_sort(int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            merge_sort(left, mid); // 왼쪽 부분 정렬
            merge_sort(mid + 1, right); // 오른쪽 부분 정렬
            merge(left, mid, right); // 병합
        }
    }

    public static void merge(int left, int mid, int right){
        int i = left;
        int j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (A[i] <= A[j]) {
                temp[k++] = A[i++]; // 작은 값을 임시 배열에 저장
            } else {
                temp[k++] = A[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = A[i++]; // 남은 왼쪽 부분 저장
        }
        while (j <= right) {
            temp[k++] = A[j++]; // 남은 오른쪽 부분 저장
        }
        for (int l = left; l <= right; l++) {
            cnt++;
            if (cnt == K) {
                answer = temp[l]; // K번째 저장된 값을 answer에 저장
                return;
            }
            A[l] = temp[l]; // 원래 배열에 정렬된 값 저장
        }
    }

    public static void solve() throws Exception {
        merge_sort(0, N - 1); // 병합 정렬 시작
        bw.write(answer + "\n"); // 결과 출력
        bw.flush(); // 출력 스트림 비우기
        bw.close(); // 출력 스트림 닫기
    }
}