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

 

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

 

---

❓
병합 정렬 알고리즘에 대해선 잘 몰랐어서 문제를 풀기 전 먼저 관련 알고리즘에 대해 공부해야 했다.

❗
병합 정렬 알고리즘이 뭔지 알면 괜찮게 풀 수 있을 듯...
난 공부를 안 해놨어서 좀 많이 헤맸다...
그래서 병합 정렬 내용을 좀 정리해봤음...

 

✨ 참고

https://hyunipad.tistory.com/124

[Java] 병합 정렬(Merge Sort)

https://www.daleseo.com/sort-merge/

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)

---

 

병합 정렬

하나의 배열을 반으로 쪼개고, 쪼개진 배열들을 또 반으로 쪼개고...

더이상 나눌 수 없을 때까지 쪼갠다. (=원소가 한 개만 남을 때까지 쪼갬)

예제 입력으로 확인해보면 아래와 같음

// 원본
[4, 5, 1, 3, 2]

// 반으로 쪼개기
[4, 5, 1]	[3, 2]

// 반으로 쪼개기
[4, 5] [1] [3] [2]

// 반으로 쪼개기
[4] [5] [1] [3] [2]

 

의사 코드

원소가 한 개만 남을 때까지 [ic]mergeSort()[/ic]가 계속 호출됨.

그리고 원소가 한 개만 남게 되면 아래와 같이 병합이 일어난다.

[4] [5] [1] [3] [2]

[4, 5] [1] [2, 3]

[1, 4, 5] [2, 3]

[1, 2, 3, 4, 5]

처음엔 이 부분이 좀 헷갈렸는데, 메모장 같은 곳에서 직접 알고리즘 따라가다 보면 이해할 수 있음

 

아래는 직접 따라가봤던 내용을 알아보기 쉽게 정리한 것

// 함수
public static void mergeSort(int p, int r) {
	if (p < r) {
		int q = (p + r) / 2;	// q는 p, r의 중간 지점
		mergeSort(p, q);	// 전반부 정렬
		mergeSort(q+1, r);	// 후반부 정렬
		merge(p, q, r);		//병합
	}
}

// 1단계
// p=0, r=4 (배열의 처음과 끝)
public static void mergeSort(int p, int r) {
	if (p < r) {
		2 = (0 + 4) / 2;	// int q = (p + r) / 2;
		mergeSort(0, 2);	// p < r이므로 재귀호출 일어남
		mergeSort(3, 4);	// p < r이므로 재귀호출 일어남
		merge(0, 2, 4);
	}
}

/*
 * 2단계
 * 1단계에서 쪼개졌던 mergeSort(0, 2), mergeSort(3, 4)가 일어남
 */
// p=0, r=2
public static void mergeSort(int p, int r) {
	if (p < r) {
		1 = (0 + 2) / 2;	// int q = (p + r) / 2;
		mergeSort(0, 1);	// p < r이므로 재귀호출 일어남
		mergeSort(2, 2);	// p == r이므로 재귀호출 일어나지 않음
		merge(0, 1, 2);
	}
}

// p=3, r=4
public static void mergeSort(int p, int r) {
	if (p < r) {
		3 = (3 + 4) / 2;	// int q = (p + r) / 2;
		mergeSort(3, 3);	// p == r이므로 재귀호출 일어나지 않음
		mergeSort(4, 4);	// p == r이므로 재귀호출 일어나지 않음
		merge(3, 3, 4);	// 합병 진행
	}
}

/*
 * 3단계
 * 2단계에서 쪼개졌던 mergeSort(0, 1)이 일어남
 */
// p=0, r=1
public static void mergeSort(int p, int r) {
	if (p < r) {
		0 = (0 + 1) / 2;	// int q = (p + r) / 2;
		mergeSort(0, 0);	// p == r이므로 재귀호출 일어나지 않음
		mergeSort(1, 1);	// p == r이므로 재귀호출 일어나지 않음
		merge(0, 0, 1);	// 합병 진행
	}
}

[ic]merge()[/ic] 함수가 언제 호출 됐는지 보면 병합 순서를 알 수 있음

이때 각 배열의 원소의 크기를 비교하고 작은 것부터 순서대로 병합 된다.

 

의사 코드

[ic][1, 4, 5] [2, 3][/ic]의 병합을 진행한다고 할 때,

처음엔 1과 2를 비교해서 더 작은 1을 tmp 배열에 갖다 붙임 (여기서 tmp 배열은 A 배열을 정렬하기 위해 쓰는 임시 배열)

그러면 [ic]i++[/ic]가 되면서 루프를 돌고 다시 4와 2를 비교하게 됨

이번엔 4보다 2가 작으므로 2가 tmp 배열에 붙으면서 [ic]j++[/ic], 다시 4와 3을 비교하게 됨

어느 한쪽 배열이 더이상 남지 않을 때까지 반복

그리고 다른 쪽 배열에 원소가 아직 남아있는 경우 tmp 배열 끝에 하나씩 갖다붙이면 됨

각각의 배열은 이미 정렬이 완료되어 있는 상태기 때문...

 

의사 코드

이제 tmp 배열의 내용을 A배열로 옮김

이건 [ic]merge()[/ic] 함수가 호출 될 때마다 발생함

그래야 중간중간 A 배열이 업데이트 되면서 정렬된 원소 간 크기 비교가 가능해지기 때문

이 부분에서 저장 횟수를 알 수 있으므로 문제를 풀 수 있다.

 

풀이

• 어느 함수에서든 A 배열에 접근할 수 있도록 static 변수로 A 배열 선언
• 마찬가지로 어느 함수에서든 사용자로부터 입력 받은 저장 횟수 K를 알 수 있도록 static 변수로 K 선언
• 전체 저장 횟수를 알고 업데이트 할 수 있도록 static 변수로 count 변수 선언
  
  • count 변수는 merge 함수가 호출 될 때마다 +1
• [ic]count == k[/ic] 일 때 저장된 수를 출력하고 프로그램 종료

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[] a;
	static int k;
	static int count = 0;
	
	// A[p..r]을 오름차순 정렬
	public static void mergeSort(int p, int r) {
		if (p < r) {
			int q = (p + r) / 2;	// q는 p, r의 중간 지점
			mergeSort(p, q);	// 전반부 정렬
			mergeSort(q+1, r);	// 후반부 정렬
			merge(p, q, r);		//병합
		}
	}
	
	/*
	 * A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
	 * A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
	 */
	public static void merge(int p, int q, int r) {
	    int i = p;
	    int j = q + 1;
	    int t = 0;
	    int[] tmp = new int[r-p+1];
	    
	    while (i <= q && j <= r) {
	        if (a[i] <= a[j]) {
	        	tmp[t++] = a[i++];
	        }
	        else {
	        	tmp[t++] = a[j++];
	        }
	    }
	    while (i <= q)	// 왼쪽 배열 부분이 남은 경우
	        tmp[t++] = a[i++];
	    while (j <= r)	// 오른쪽 배열 부분이 남은 경우
	        tmp[t++] = a[j++];
	    
	    i = p;	t = 0;
	    
	    while (i <= r) {	// 결과를 A[p..r]에 저장
	        a[i++] = tmp[t++];
	        count++;
	        
	        if (count == k) {
	        	System.out.println(a[i-1]);	// a[i++]로 i가 1 커진 상태이므로 하나 빼줌
	        	System.exit(0);
	        }
	    }
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());	// 배열 A 크기
		k = Integer.parseInt(st.nextToken());	// 저장 횟수
		a = new int[n];	// 배열 A
		
		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(-1);
	}

}

최선의 코드는 아니지만 일단 올려봄...