[백준] 24060 알고리즘 수업 - 병합 정렬 1 - 정렬(Sort) + 분할정복(DivideAndConquer) JAVA

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

코드설명

정렬(Sort) + 분할정복(DivideAndConquer) 을 활용합니다.

 

K번쨰 저장되는 숫자를 구하기 위해서는 단순히 병합정렬을 구현한뒤 병합정렬에 값이 저장되는 순간을 한개씩 증가시키면서 K번째일떄 해당 답을 저장하면 됩니다.

코드

먼저, 병합정렬을 구현해보았습니다.

병합정렬은 여러가지 방식으로 구현가능한데요, 일단은 int[] 를 반환하여서 직접 배열을 반환하는 방식으로 구현했습니다.

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

public class Main {
	private static int C, N, M, W, H, K;
    private static int answer = 0;
    private static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine());
        
        arr = mergeSort(new int[] {1, 111, 111, 121, 5, 99, 2, 4, 6, 100}, 0, 7);
        for(int v : arr ) {
        	System.out.println(v);
        }
        
        
    }
    
    //mergeSort는 병합하면서 정렬하는 방식이다.
    //즉, 먼저 분할을 해줘야한다는 것 이다.
    private static int[] mergeSort(int[] A, int left, int right) {
    	//만약 사이즈가 같아진다면, 1개만 남았으므로 반환한다.
    	if(left >= right) {
    		return new int[] {A[left]};
    	}
    	
//    	0 1 2 3 4 5 6 7 
//    	mid는 7/2 = 3.5. 3이라 생각.
//    	
//    	0 1 2 3 4 5 6
//    	mid는 6/2 = 3. 3 이라 생각.
    	//먼저, 2개로 나누는 과정이다.
    	int mid = (left + right) / 2;
    	int[] leftArr = mergeSort(A, left, mid);
    	int[] rightArr = mergeSort(A, mid + 1, right);
    	
    	return merge(leftArr, rightArr); 
    }
    
    //
    private static int[] merge(int[] left, int[] right) {
    	int[] mergedArr = new int[left.length + right.length];
    	int mergedIdx = 0;
    	int leftIdx = 0, rightIdx = 0;
    	while(leftIdx < left.length && rightIdx < right.length) {
//    		while(leftIdx < left.length && rightIdx < right.length && left[leftIdx] < right[rightIdx]) {
//    			mergedArr[mergedIdx++] = left[leftIdx];
//    			leftIdx++;
//    		}
//    		while(leftIdx < left.length && rightIdx < right.length && right[rightIdx] < left[leftIdx]) {
//    			mergedArr[mergedIdx++] = right[rightIdx];
//    			rightIdx++;
//    		}
    		
    		if(left[leftIdx] <= right[rightIdx]) {
    			mergedArr[mergedIdx++] = left[leftIdx++];
    		}
    		else if(left[leftIdx] > right[rightIdx]) {
    			mergedArr[mergedIdx++] = right[rightIdx++];
    		}
    	}
    	//아직 다 못한것들. 
    	while(leftIdx < left.length) {
    		mergedArr[mergedIdx++] = left[leftIdx];
			leftIdx++;
    	}
    	while(rightIdx < right.length) {
    		mergedArr[mergedIdx++] = right[rightIdx];
			rightIdx++;
    	}
    	return mergedArr;
    }
    
}

 

정답코드1 입니다

package Main;

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

public class Main {
	private static int C, N, M, W, H, K;
    private static int answer = 0;
    private static int[] arr;
    private static int mergedCnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        mergeSort(arr, 0, arr.length - 1);
        
        if(mergedCnt < K) System.out.println(-1);
        else System.out.println(answer);
        
        
    }
    
    //mergeSort는 병합하면서 정렬하는 방식이다.
    //즉, 먼저 분할을 해줘야한다는 것 이다.
    private static int[] mergeSort(int[] A, int left, int right) {
    	//만약 사이즈가 같아진다면, 1개만 남았으므로 반환한다.
    	if(left >= right) {
    		return new int[] {A[left]};
    	}
    	
//    	0 1 2 3 4 5 6 7 
//    	mid는 7/2 = 3.5. 3이라 생각.
//    	
//    	0 1 2 3 4 5 6
//    	mid는 6/2 = 3. 3 이라 생각.
    	//먼저, 2개로 나누는 과정이다.
    	int mid = (left + right) / 2;
    	int[] leftArr = mergeSort(A, left, mid);
    	int[] rightArr = mergeSort(A, mid + 1, right);
    	
    	return merge(leftArr, rightArr); 
    }
    
    //
    private static int[] merge(int[] left, int[] right) {
    	int[] mergedArr = new int[left.length + right.length];
    	int mergedIdx = 0;
    	int leftIdx = 0, rightIdx = 0;
    	while(leftIdx < left.length && rightIdx < right.length) {
//    		while(leftIdx < left.length && rightIdx < right.length && left[leftIdx] < right[rightIdx]) {
//    			mergedArr[mergedIdx++] = left[leftIdx];
//    			leftIdx++;
//    		}
//    		while(leftIdx < left.length && rightIdx < right.length && right[rightIdx] < left[leftIdx]) {
//    			mergedArr[mergedIdx++] = right[rightIdx];
//    			rightIdx++;
//    		}
    		
    		if(left[leftIdx] <= right[rightIdx]) {
    			if(++mergedCnt == K) {
    				answer = left[leftIdx];
    			}
    			mergedArr[mergedIdx++] = left[leftIdx++];
    		}
    		else if(left[leftIdx] > right[rightIdx]) {
    			if(++mergedCnt == K) {
    				answer = right[rightIdx];
    			}
    			mergedArr[mergedIdx++] = right[rightIdx++];
    		}
    	}
    	//아직 다 못한것들. 
    	while(leftIdx < left.length) {
    		if(++mergedCnt == K) {
				answer = left[leftIdx];
			}
    		mergedArr[mergedIdx++] = left[leftIdx];
			leftIdx++;
    	}
    	while(rightIdx < right.length) {
    		if(++mergedCnt == K) {
				answer = right[rightIdx];
			}
    		mergedArr[mergedIdx++] = right[rightIdx];
			rightIdx++;
    	}
    	return mergedArr;
    }
    
}

 

두번쨰 정답코드입니다.

문제의 의사코드를 참고하여 구현했습니다. 사실, 이 코드가 merge 부분에서만 [] 을 생성하여 처리하므로 더 빠를 줄 알았는데, 실제로 비교해보면 시간은 거의 똑같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	private static int C, N, M, W, H, K;
    private static int answer = 0;
    private static int[] arr;
    private static int mergedCnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        mergeSort(arr, 0, arr.length - 1);
        //System.out.println(mergedCnt);
        
        if(mergedCnt < K) System.out.println(-1);
        else System.out.println(answer);
        
        
    }
    
    private static void mergeSort(int[] A, int lo, int hi) {
    	if(lo == hi) {
    		return ;
    	}
    	
    	//분할한다.
    	int mid = (lo + hi)/2;
    	mergeSort(A, lo, mid);
    	mergeSort(A, mid + 1, hi);
    	
    	//합친다.
    	merge(A, lo, mid, hi);
    	return ;
    	
    }
    
    private static void merge(int[] A, int lo, int mid, int hi) {
    	int[] temp = new int[hi - lo + 1];
    	int tempIdx = 0;
    	int left = lo;
    	int right = mid + 1;
    	while(left <= mid && right <= hi) {
    		if(A[left] < A[right]) {
    			if(++mergedCnt == K) {
    				answer = A[left];
    			}
    			temp[tempIdx++] = A[left++];
    		}else {
    			if(++mergedCnt == K) {
    				answer = A[right];
    			}
    			temp[tempIdx++] = A[right++];
    		}
    	}
    	
    	while(left <= mid) {
    		if(++mergedCnt == K) {
				answer = A[left];
			}
    		temp[tempIdx++] = A[left++];
    	}
    	while(right <= hi) {
			if(++mergedCnt == K) {
				answer = A[right];
			}
    		temp[tempIdx++] = A[right++];
    	}
    	
    	for(int i=lo; i<=hi; i++) {
    		A[i] = temp[i - lo];
    	}
    }
 
}