[BAEKJOON] 24060 알고리즘 수업 - 병합 정렬 1

병합정렬 

병합정렬은 정렬 알고리즘중 하나이다. 병합 정렬의 자세한 내용은 아래 사이트에 참조 하면 된다.

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

문제 요약

• 알고리즘 분류: 정렬, 재귀
• 난이도: Silver4
• 문제내용:
  • 문자열길이를 출력한다.
• 사이트 주소: https://www.acmicpc.net/problem/24060

24060번: 알고리즘 수업 - 병합 정렬 1

문제풀이

1. 위에 문제 코드를 각 언어에 맞게 작성한다.
2. 배열 A, tmp, count, 결과값을 전역변수로 설정한다. → 배열로 지역변수로 설정시 메모리와 시간을 차지한다.
3. 위에 코드 작성후 K번째 저장 되는 수를 구하기 위해서 merge함수의 병합정렬 결과에 count증가와 count와 K번째 수가 일치 할 경우 K번째 수를 저장한다.
4. 재귀 호출시 중간에 K번째 수를 찾을 경우 리턴하는 코드를 추가한다. → why? 루프 탈출 안 할시 시간 초과 될 경우가 있다.

코드

Python

def merge_sort(A, p, r):
    if(p < r and count <= K):
        q = (p + r) // 2;
        merge_sort(A, p , q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)
        
def merge(A, p, q, r):
    global count, result
    i, j = p, q + 1
    tmp = []
    
    while i <= q and j <= r:
        if(A[i] <= A[j]):
            tmp.append(A[i])
            i += 1
        else:
            tmp.append(A[j])
            j += 1
        
    while i <= q:
        tmp.append(A[i])
        i += 1
    
    while j <= r:
        tmp.append(A[j])
        j += 1
    
    i, t = p, 0;
    
    while i <= r:
        A[i] = tmp[t]
        count += 1
        if count == K:
            result = A[i]
            break;
        i += 1
        t += 1

N, K = map(int, input().split())
A = list(map(int, input().split()))
count = 0
result = -1
merge_sort(A, 0, N - 1)
print(result)

Java

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


public class Main {
	
	static int[] A, tmp;
	static int count = 0;
	static int result = -1;
	static int K;
	
	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());
		K = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		A = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		tmp = new int[N];
		merge_sort(A, 0, N - 1);
		System.out.println(result);
		
	}
	
	public static void merge_sort(int[] A, int p, int r) {
		if (count > K) return ;
		if (p < r) {
			int q = (p + r) / 2;
			merge_sort(A, p, q);
			merge_sort(A, q + 1, r);
			merge(A, p, q, r);
		}
	}
	
	public static void merge(int[] A, int p, int q, int r) {
		int i = p;
		int j = q + 1;
		int t = 0;
		
		while (i <= q && j <= r) {
			if(A[i] <= A[j]) {
				tmp[t] = A[i];
				i++;
			}else {
				tmp[t] = A[j];
				j++;
			}
			t++;
		}
		
		while (i <= q) 
			tmp[t++] = A[i++];

		while (j <= r) 
			tmp[t++] = A[j++];

		i = p;
		t = 0;
		while (i <= r) {
			count++;
			if (count == K) {
				result = tmp[t];
				break;
			} 
			A[i++] = tmp[t++];
		}
	}
	
}