짧은머리 개발자

지난 글에 이어서 이번 글은 배열을 이용해 최소 최대를 구할 것이다.

아니 근데 아무생각 없이 Bubble Sort를 이용해서 문제를 풀었더니 시간초과가 발생했다. 아 ㅋㅋ 부끄럽다 ㅋㅋ

아니 근데 ㅋㅋㅋ QuickSort를 했을 때도 시간초과가 발생했다. 이게 무슨일이고!

Merge Sort는 정상적으로 정답이 나오는 것 보니, QuickSort의 최악의 경우가 n^2이라 그런 것 같다. 아마 테스트케이스에 정렬이 거의 다 되어있는 녀석이 있는거겠지.. 휴

문제풀이

여튼! 본론으로 돌아가서 문제풀이를 해 보자.

문제의 내용은 똑같으니, 앞 글에서 확인해주길 바라며 이 글에서는 본의아니게 Merge Sort에 대해 다루겠다

MergeSort, Divide and Conquer

MergeSort, 병합정렬은 쪼개고 합치는 행위로 수행된다.

정렬하고자 하는 배열 혹은 리스트가 주어지면, 더 이상 쪼갤 수 없을 때 까지 쪼갠다. 그리고 나서 다시 합쳐야 하는데, 이 때 더 이상 쪼갤 수 없는 단위까지 쪼갰기 때문에 두 수만 비교하여 정렬하면서 다시 배열을 만들면 된다.

2개를 넘어가는 수에서 합칠때 비교 방법은 다음과 같다.

M번째 요소: 좌측 혹은 우측에서 증가한 자리. 예를 들어, 좌측에서 1번째 요소를 이미 썼다면 M번째 요소는 2번째. 우측도 마찬가지. 이 때, 좌측과 우측의 M번째는 각각 독립적이다.

1. 좌측 배열의 인덱스가 마지막 까지 갔다면, 우측 배열의 M번째 요소를 선택한다.
2. 우측 배열의 인덱스가 마지막 까지 갔다면, 좌측 배열의 M번째 요소를 선택한다.
3. 좌측 배열의 값이 우측 배열의 값보다 작다면 좌측 배열의 M번째 요소를 선택한다.
4. 우측 배열의 값이 좌측 배열의 값보다 작다면 우측 배열의 M번째 요소를 선택한다.

코드를 보면 알겠지만, 각각의 요소를 모두 비교하여 선택하는 방식이다.

이 때, Merge Sort의 복잡도는 O(n logn)이 된다. 이 때, O(n)은 배열 전체에 대한 시간이고, O(log n)은 전체에 대하여 절반으로 나누었기 때문이다.

$$ T(N) = 2 * T(N/2) + N $$ 이고, N/2를 대입하면 $$ T(N/2) = 2 * T(N/4) + {N/2} ... $$가 된다. 반복하여 이를 정리하면, $$ T(N) = 2^n * T( {N / 2^n }) + n*N $$

최종 코드

import java.util.Scanner;

public class Number10818Arr {
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int arr[] = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = scan.nextInt();
        }
        int arr2[] = new int[N];
        sort(arr, 0, N-1, arr2);
        System.out.println(arr[0] + " " + arr[N-1]);
    }

    static void sort(int A[], int low, int high, int B[]){
        if(low >= high) return;

        int mid = (low + high) / 2;

        sort(A, low, mid, B);
        sort(A, mid+1, high, B);

        int i=low, j=mid+1;
        for(int k = low; k <= high; ++k){
            if(i > mid)
            	B[k] = A[j++];
            else if(j > high)
            	B[k] = A[i++];
            else if(A[i] <= A[j])
            	B[k] = A[i++];
            else
            	B[k] = A[j++];
        }

        for(i = low; i <= high; ++i)
        	A[i] = B[i];
    }
}

결과는 정답!

Merge Sort에 관한 글은 새로 정리해서 추가로 올리겠다.

이번엔 백준 10818번 문제를 풀려한다. 이 문제는 굳이 [배열]에 분류되었어야 하나 싶은 문제다.

따라서 배열을 쓰지 않고 푸는 방법, 배열을 쓰고 푸는 방법 총 두 가지로 풀 예정이다.

우선 지금은 배열을 쓰지 않고 풀 것이다. 테스트 케이스가 몇 개인지 주어졌기 때문에, 해당 횟수만큼 숫자를 입력받고, 최대 최소를 결정하면 된다.

최솟값은 1000001, 최댓값은 -1000001로 초기화시킨다.
그 이유는 이 값들은 입력될 범위보다 크거나 작기 때문에, 어떤 수도 1000001보다 작고, -1000001보다 크기 때문이다.

위처럼 최소, 최댓값을 초기화 시키고, 앞으로 들어오는 수에 대하여 최소보다 작다면 최솟값을 갱신시킨다. 마찬가지로 최대보다 크다면 최댓값을 갱신시킨다.

이를 통해 배열에 굳이 숫자를 집어넣지 않고도 계산이 가능하다.

최종 코드

import java.util.Scanner;

public class Number10818 {
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int min = 1000001, max = -1000001;
        for(int i = 0; i < N; i++){
            int cur = scan.nextInt();
            min = (Math.min(cur, min));
            max = (Math.max(cur, max));
        }

        System.out.println(min + " " + max);
    }
}

결과는 정답!