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

24060번: 알고리즘 수업 - 병합 정렬 1 (acmicpc.net)

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

 

- N개의 서로 다른 양의 정수가 저장된 배열 A가 있다.

- 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 k번째 저장되는 수를 구하기 

- 저장 횟수가 k보다 작으면 -1 출력

 

풀이 과정 

 

병합 정렬 알고리즘 

 

- 배열의 요솟수가 2개 이상인 경우 

   - 배열의 앞부분을 병합 정렬로 정렬

   - 배열의 뒷부분을 병합 정렬로 정렬 

   - 배열의 앞부분과 뒷부분을 병합 

 

- 주어진 리스트를 절반으로 분할하여 부분 리스트로 나눔(Divide : 분할)

- 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이 

- 인접한 부분리스트끼리 정렬하여 합침 (Conqure: 정복)

 

병합 정렬 의사 코드 

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

 

 

풀이 과정 

 

[BAEKJOON] 24060 알고리즘 수업 - 병합 정렬 1 (tistory.com)

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

- 배열 A에 저장하는 횟수가 k가 되면 병합 정렬을 종료 

- merge가 호출하는 횟수가 k가 되면 호출횟수와 저장되는 숫자를 출력 

 

- 배열 A, temp, count, 결과값을 전역 변수로 설정

- 병합정렬 코드 작성 후 k번째 저장되는 수를 구하기 위해서 merge 함수의 병합 정렬 결과에 count 증가와 count와 k번째 수가 일치할 경우 k번째 수를 저장 

- 재귀 호출 시 중간에 k번째 수를 찾을 경우 리턴하는 코드 추가 

 

 

정답 

 

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

public class Main {
    static int count = 0;
    static int tmp[];
    static int A[];
    static int result = -1;
    static int k;
    
    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++];
			}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) {
			count++;
            if(count == k)
            {
                result = tmp[t];
                break;
            }
            A[i++] = tmp[t++];
			}
	}
    
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        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);
        bw.write(result+"");
        
        bw.flush();
        bw.close();
        
    }
}