백준 알고리즘 24060번: 알고리즘 수업 [Java]

문제 출처: https://www.acmicpc.net/problem/24060

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

1. 코드

import java.util.*;

class MergeArray{
	int[] A;
	private int[] tmp;
	private int k;
	private int cnt;
	public void merge_sort(int p, int r) {		//배열 A를 클래스 멤버 변수로
		int q;
	    if (p < r) {
	        q = (p + r) / 2;
	        merge_sort(p, q);
	        merge_sort(q + 1, r);
	        merge(p, q, r);
	    }
	}
	
	private void merge(int p, int q, int r) {
		int i = p;
		int j = q + 1;
		int t = 0;				//배열은 0부터 시작하기에 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) {
	    	A[i++] = tmp[t++];
	    	cnt++;
	    	if(cnt == k) {
	    		System.out.println(A[i - 1]);
	    		System.exit(0);
	    	}
	    }
	}
	
	MergeArray(int n, int k){
		A = new int[n];
		tmp = new int[n];
		this.k = k;
		cnt = 0;
	}
}

class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	
    	MergeArray m = new MergeArray(n, k);
    	for(int i = 0; i < n; i++)
    		m.A[i] = sc.nextInt();
    	m.merge_sort(0, n - 1);				//배열은 0부터 n-1까지이기 때문에
    	System.out.println(-1);
    	sc.close();
    }
}

(실행)

2. 풀이

class MergeArray{
	int[] A;
	private int[] tmp;
	private int k;
	private int cnt;

자바에는 안전성의 이유로 참조에 의한 호출이 안되는 것으로 알고 있다. 따라서 클래스를 활용하여 배열을 만들어준다.

public void merge_sort(int p, int r) {		//배열 A를 클래스 멤버 변수로
    int q;
    if (p < r) {
    	q = (p + r) / 2;
        merge_sort(p, q);
        merge_sort(q + 1, r);
        merge(p, q, r);
    }
}

배열 A는 클래스의 멤버 변수로서 존재하기에 메소드의 매개변수는 지워준다.

	private void merge(int p, int q, int r) {
		int i = p;
		int j = q + 1;
		int t = 0;			//배열은 0부터 시작하기에 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) {
	    	A[i++] = tmp[t++];
	    	cnt++;
	    	if(cnt == k) {
	    		System.out.println(A[i - 1]);
	    		System.exit(0);
	    	}
	    }
	}

변수 t는 tmp 배열의 인덱스를 가리키는 역할을 하며 배열의 인덱스는 0부터 시작하므로 0으로 초기화를 해준다. 그리고 k번째 저장되는 수를 출력해주고 프로그램을 종료한다.

MergeArray(int n, int k){
	A = new int[n];
	tmp = new int[n];
	this.k = k;
	cnt = 0;
}

생성자에서 반복문을 활용하여 Scanner를 통해서 입력하여 배열 A를 초기화를 하는 것은 이클립스 컴파일러에서는 진행이 가능했지만 백준에서 채점할 시 런타임에러가 발생하여 생성자에서는 진행하지 않았다.

class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	
    	MergeArray m = new MergeArray(n, k);
    	for(int i = 0; i < n; i++)
    		m.A[i] = sc.nextInt();
    	m.merge_sort(0, n - 1);		//배열은 0부터 n-1까지이기 때문에
    	System.out.println(-1);
    	sc.close();
    }
}

merge_sort 함수에서 배열의 범위를 전달하는 것이기에 0과 n-1를 보낸다. 만약 merge_sort 함수에서 정답이 출력되지 않는다면 저장 횟수보다 k가 높다는 것이기에 -1을 출력해준다.

3. 느낀점

문제 자체는 쉬운 문제였는데 생각지도 못했던 런타임 에러를 해결하는 데 시간이 걸렸다.