백준 Q24060 - 알고리즘 수업 - 병합정렬 1

유동우·2025년 1월 30일

Problem Solving with Baekjoon

목록 보기

19/20

문제 및 입출력

풀이

static int K;
static int[] temp;
static int result = -1;
static int cnt = 0;

다양한 메서드에서 공통으로 사용할 변수들을 정적으로 선언해놓는다
이때 result 변수는 기본 출력값은 -1 이므로 -1로 초기화를 했다

K: 오름차순 정렬 진행 중 배열에 K번째 입력되는 수를 구하기 위한 입력값
temp: 정렬 진행 중 임시로 수를 저장하기 위한 배열
result: K번째로 저장되는 수
cnt: K와 비교하기 위한 카운트

private static void mergeSort(int[] a, int start, int end) {
	if (start < end) {
    	int mid = (start + end) / 2;
		mergeSort(a, start, mid);
		mergeSort(a, mid + 1, end);
		merge(a, start, mid, end);
	}
}

문제에 주어진 합병정렬 수도코드 그대로 작성하였다
재귀를 사용하여 중간값을 기준으로 좌,우를 나누어 각각 다시 병합하는 과정이 담겨져있다

private static void merge(int[] a, 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++];
		}

		t=0;
		i = start;

		while(i <= end) {
			cnt++;
			if (cnt == K) {
				result = temp[t];
				break;
			}
			a[i++] = temp[t++];
		}
	}

합치는 과정의 메서드인 merge메서드는 수도코드에 약간 변형이 있었다
문제에서 주어진대로 정렬 과정에서 K번째인 수를 찾기위해 cnt 값과 비교하여 K번째 수와 같으면 break문을 사용하여 바로 result에 담아 출력을 진행하였다

이때 주의해야 될 점이 처음에는 cnt를 정적변수에서 선언만하고 해당 메서드에서 cnt=0으로 계속 초기화를 했더니 result에 -1만 담겨 출력되는 사고가 발생하였다

merge 메서드는 배열의 각 좌,우 부분을 재귀를통하여 계속 호출되며 합치는 메서드이므로 각 스텝마다 공유하기 위해 static cnt 로 선언한건데 이를 잠깐 망각하여 시간이 오래걸렸다

최종 코드

public class Main {
	static int K;
	static int[] temp;
	static int cnt = 0;
	static int result = -1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int size = Integer.parseInt(st.nextToken());
		int[] arr = new int[size];
		K = Integer.parseInt(st.nextToken());
		temp = new int[size];

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

		mergeSort(arr, 0, arr.length - 1);

		System.out.println(result);
	}

	private static void mergeSort(int[] a, int start, int end) {
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(a, start, mid);
			mergeSort(a, mid + 1, end);
			merge(a, start, mid, end);
		}
	}

	private static void merge(int[] a, 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++];
		}

		t=0;
		i = start;

		while(i <= end) {
			cnt++;
			if (cnt == K) {
				result = temp[t];
				break;
			}
			a[i++] = temp[t++];
		}
	}
}