24060번

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

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

이 문제는 조금 별로인 것 같다. 객체 지향적으로 코딩을 하면 시간 초과가 나와서 모든 메서드를 static으로 만들어야 한다.

문제에 주어진 의사코드를 바탕으로 코드를 짠뒤에 변화하는 횟수를 세면서 k번째가 되면 그때 변화시킨 숫자를 출력하는 문제인데

지속적인 시간초과로 다른 사람들의 코드를 볼 수 밖에 없었다... 원인은 클래스를 따로 만들어서 실행하다보니 매번 일시저장 배열을 만들어서 그에 따른 시간소모로 시간초과가 난 것으로 예상된다.

먼저, 병합정렬 코드는 아래와 같다. 재귀함수를 이용하여 배열의 요소가 1개가 될때까지 나누고, 다시 작은 값부터 합치는 방식이다.

public static void mergesort(int[] arr, int start, int end){
    if(start<end) {
        int q = (start + end) / 2;
        mergesort(arr, start, q);
        mergesort(arr, q + 1, end);
        merge(arr, start, q, end);
    }

합치는 과정을 위해 필요한 부분이 아래의 코드이다.

public static void merge(int[] arr,int start, int q, int end){
    int i = start;
    int j = q+1;
    int t = 0;
    while (i<=q && j<=end){
        if(arr[i]<=arr[j]){
            tmp[t++]=arr[i++];
        }else tmp[t++]=arr[j++];
    }
    while (i<=q){
        tmp[t++]=arr[i++];
    }//앞의 배열 요소가 남았을 때
    while (j<=end){
        tmp[t++]=arr[j++];
    }//뒤의 배열 요소가 남았을 때
    i=start;
    t=0;
    while (i<=end){
        arr[i++]=tmp[t++];
        count++;
        if(count==k){
            result=arr[i-1];
            break;
        }
    }
}

정렬되어있는 앞의 배열과 뒤의 배열의 요소들을 비교하여, 합치는 과정이다.

두 배열을 합치고 나면 남는 요소들이 있을 것이고 그것 또한 배열에 넣어주기 위해 while문을 2개 더 쓴것이다.

이후 배열을 다시 채우는 과정을 하는데 배열을 채울 때마다 count값을 증가시켜서 원래 배열에서 변화시킨 횟수를 센다.

그렇게 횟수를 세다가 k의 값과 같으면 출력하고 그렇지 않고, k의 값이 다 끝난 후 count값보다 크면 -1을 출력하는 것이다.

 

그래서 정답 코드는 아래와 같다.

package backjoon.b24060;

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

public class b24060 {
    static int[] tmp;
    static int count =0;
    static int k;
    static int result = -1;

    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());
        int[] arr = new int[n];
        tmp = new int[n];
        for(int i=0; i<n;i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }
        br.close();
        mergesort(arr,0,n-1);
        System.out.println(result);
    }

    public static void mergesort(int[] arr, int start, int end){
        if(start<end) {
            int q = (start + end) / 2;
            mergesort(arr, start, q);
            mergesort(arr, q + 1, end);
            merge(arr, start, q, end);
        }
    }
    public static void merge(int[] arr,int start, int q, int end){
        int i = start;
        int j = q+1;
        int t = 0;
        while (i<=q && j<=end){
            if(arr[i]<=arr[j]){
                tmp[t++]=arr[i++];
            }else tmp[t++]=arr[j++];
        }
        while (i<=q){
            tmp[t++]=arr[i++];
        }
        while (j<=end){
            tmp[t++]=arr[j++];
        }
        i=start;
        t=0;
        while (i<=end){
            arr[i++]=tmp[t++];
            count++;
            if(count==k){
                result=arr[i-1];
                break;
            }
        }
    }

}