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

guswls·2024년 5월 9일

구현 백준

알고리즘

목록 보기

24/39

문제

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

코드

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

class Main {
	static int N;
	static int K;
	static int count = 0;
	static int result = -1;
	static int[] A;
	static int[] temp;

	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());
		A = new int[N];
		temp = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		mergeSort(0, N - 1);

		System.out.println(result);
	}

	static void mergeSort(int start, int end) {
		if (count > K) {
			return;
		}

		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(start, mid);
			mergeSort(mid + 1, end);
			merge(start, mid, end);
		}
	}

	static void merge(int start, int mid, int end) {
		int i = start;
		int j = mid + 1;
		int t = 0;

		while (i <= mid && j <= end) {
			if (A[i] <= A[j]) {
				temp[t++] = A[i++];
			} else {
				temp[t++] = A[j++];
			}
		}

		while (i <= mid) {
			temp[t++] = A[i++];
		}

		while (j <= end) {
			temp[t++] = A[j++];
		}

		i = start;
		t = 0;

		while (i <= end) {
			++count;

			if (count == K) {
				result = temp[t];
				return;
			}

			A[i++] = temp[t++];
		}
	}
}

문제 이해

병합 정렬의 과정에서 배열 A에 K번째로 저장되는 수를 구하는 문제이다.
병합 정렬의 sudo코드가 그대로 문제에 나와있기 때문에 이를 그대로 구현하면 된다.

풀이 방법

sudo코드 대로 병합정렬을 구현하되, 문제에서 요구하는 K번째로 배열에 들어가는 값을 어떻게 구할 지 생각해야 한다.
코드를 보면 temp 배열의 값이 A배열로 복사되는 부분은 merge 메서드 마지막 부분 while루프에 존재한다.
따라서 이 루프가 수행되는 회수를 count로 갱신하면서 이 count가 K인 시점에 temp[t]를 구하면 된다.

핵심 포인트

만약 문제에서 나온 그대로 구현한다면 시간초과가 발생할 가능성이 높다.
temp배열을 static으로 미리 생성한 후 관리해야 시간초과가 발생하지 않는다.
merge의 수행횟수가 많은 경우, 매번 매 순간 temp배열을 초기화 하는 비용이 큰것 같다.

보완할 점 / 느낀 점

sudo코드를 그대로 구현하면 되는 문제이기에 크게 어려운 문제는 아니었다.
다만 만약 이 문제에 sudo코드가 주어지지 않았다면, 문제를 해결하는 것이 굉장히 힘들었을 것이라 추측된다.
재귀에 관한 로직은 세그먼트 트리같은 트리의 초기화 로직과 비슷하기에 이해가 쉬웠는데 merge메서드는 직접 실행을 따라가봐야 이해할 수 있었다.
나중에 각 정렬 방법에 대해서도 코드로 정리하는 시간을 가져봐야겠다.
그리고 구현은 맞았음에도, 핵심 포인트에서 언급한 것과 같이 시간 초과가 발생했다.
이런 부분에 대해서도 조심해야겠다.