서론
처음 문제를 접했을 때는 병합정렬에 대해 잘 알지 못했습니다. 그래서 따로 병합정렬에 대해서 정리를 해보려고합니다
⭕병합정렬에 대해서 정리한 글 링크입니다!
https://velog.io/@sunset_1839/%EC%9E%90%EB%B0%94JAVA-%EB%B3%91%ED%95%A9%ED%95%A9%EB%B3%91-%EC%A0%95%EB%A0%AC-Merge-sort
이 문제는 배열과 정수 K를 입력받고 병합정렬 과정중 배열에 K번째로 저장된 값을 찾으면 해결되는 문제였습니다. 병합정렬에 대한 코드도 예시로 있었지만 이해하기는 쉽지 않았던것 같습니다😅.
하지만 런타임 에러 (시간초과)가 계속 나왔기에 이에 대한 해결을 해보려고 노력했습니다.
입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
출력
배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.
예제 입력 1
5 7
4 5 1 3 2
예제 출력 1
3
예제 입력 2
5 13
4 5 1 3 2
예제 출력 2
-1
저장 횟수 12가 K 보다 작으므로 -1을 출력한다.
문제 해결 과정
1.틀린 원인 찾기
처음 제출한 코드에는 입력 데이터들과 출력결과가 올바르게 나왔지만, 자꾸 런타임 에러가 나왔습니다. 그래서 원인을 찾아보았는데 제 생각엔
merge함수내에서temp 배열을 계속해서 생성하고 있었습니다.- K번째로 저장된 값을 찾았다면 루프와 함수를 중단을 해야 된다고 생각했습니다.
<최초 제출 코드>
public class Main {
static int count = 0;
static int K = 0;
static int result = 0;
private static void merge_sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2; //배열의 중앙구하기
merge_sort(arr, left, mid); //전반부 정렬
merge_sort(arr, mid + 1, right); //후반부 정렬
merge(arr, left, mid, right); //병합작업
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[arr.length];
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int index = left; index < k; index++) {
count++;
if (count == K) {
result = temp[index];
}
arr[index] = temp[index];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int[] arr = new int[A];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < A; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
merge_sort(arr,0,arr.length-1);
if (count < K) {
System.out.println(-1);
} else {
System.out.println(result);
}
}
}2.문제 해결
-
전역 배열 사용으로 메모리 효율성 개선
merge함수에서 반복적으로 생성하던temp[]배열을 배열을 전역으로 선언하고 한 번만 할당한 후, 모든 병합 과정에서 재사용합니다. 배열을 매번 생성하지 않고 한 번만 생성해 사용하므로 메모리 할당과 해제에서 발생하는 오버헤드를 줄여 성능이 향상됩니다. -
불필요한 연산 중단
count > K인 경우, 즉 K번째 값이 결정된 후에는 더 이상 정렬이나 병합 과정을 진행하지 않도록 합니다. merge_sort 함수에 if(count > K) return; 조건을 추가해, K번째 값이 결정되면 바로 재귀 호출을 중단합니다. 이를 통해 불필요한 연산을 방지하여 속도가 빨라졌습니다. -
조건문에서 성능 향상
정렬 배열에 임시 배열의 값들을 저장하는 과정에서count == k조건을 찾을 시 반복문을 종료시킨다.
<최종 제출 코드>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int K,count = 0;
static int result = -1;
static int temp[],arr[];
private static void merge_sort(int[] arr, int left, int right) {
if(count > K) return;
if (left < right) {
int mid = (left + right) / 2; //배열의 중앙구하기
merge_sort(arr, left, mid); //전반부 정렬
merge_sort(arr, mid + 1, right); //후반부 정렬
merge(arr, left, mid, right); //병합작업
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int index = left; index < k; index++) {
++count;
arr[index] = temp[index];
if (count == K) {
result = temp[index];
break;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
temp = new int[A]; //임시 배열
arr = new int[A]; //정렬 배열
st = new StringTokenizer(br.readLine());
for (int i = 0; i < A; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
merge_sort(arr,0,arr.length-1);
System.out.println(result);
}
}
