[백준] 2751 (수 정렬하기 2)

#1 알고리즘

병합 정렬 (Merge Sort)

정렬 알고리즘은 여러 가지가 있다. 상황에 맞추어 가장 적절한 알고리즘을 골라야 하지만, 나는 알고리즘을 공부 중이므로 사용해 보지 않은 정렬 알고리즘 중에 아무거나 골라서 사용한다. 이 문제에 사용할 알고리즘은 병합 정렬(Merge Sort)이다.

 

#2 코드

#2-1 자바

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int arrayLength = Integer.parseInt(br.readLine());
        
        int[] array = new int[arrayLength];
        for(int i = 0; i < arrayLength; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        
        br.close();
        
        mergeSort(array, 0, (arrayLength - 1));
        
        for(int sortedElement : array) {
            bw.write(Integer.toString(sortedElement) + "\n");
        }
        bw.flush();
        
        bw.close();
    }

    private static void mergeSort(int[] array, int startIndex, int endIndex) {
    
        // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
        if(startIndex < endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
            mergeSort(array, startIndex, midIndex);
            mergeSort(array, (midIndex + 1), endIndex);
            
            merge(array, startIndex, midIndex, endIndex);
        }
    }

    private static void merge(int[] array, int startIndex, int midIndex, int endIndex) {
        // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
        int f = startIndex; // f의 최댓값은 midIndex
        
        // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
        int s = midIndex + 1; // s의 최댓값은 endIndex
        
        // Temporary 배열 그리고 이 배열을 순회할 인덱스 t
        int[] T = new int[endIndex - startIndex + 1];
        int t = 0;
        
        while(f <= midIndex && s <= endIndex) {
            
            if(array[f] < array[s]) {
                T[t++] = array[f++];
                
            } else {
                T[t++] = array[s++];
                
            }
        }
        
        while(f <= midIndex) {
            T[t++] = array[f++];
        }
        
        while(s <= endIndex) {
            T[t++] = array[s++];
        }
        
        for(int i = 0; i < T.length; i++) {
            array[startIndex + i] = T[i];
        }
        
    }
}

 

#2-2 코틀린

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val arraySize = br.readLine().toInt()
    val array : Array<Int> = Array(arraySize) { 0 }
    for(i : Int in 0..<arraySize) {
        array[i] = br.readLine().toInt()
    }

    br.close()
    
    mergeSort(array, 0, (arraySize - 1))

    for(sortedElement : Int in array) {
        bw.write("$sortedElement\n")
    }
    bw.flush()
    
    bw.close()
}

fun mergeSort(array: Array<Int>, startIndex : Int, endIndex : Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if(startIndex < endIndex) {
        val midIndex = (startIndex + endIndex) / 2
        mergeSort(array, startIndex, midIndex)
        mergeSort(array, (midIndex + 1), endIndex)

        merge(array, startIndex, midIndex, endIndex)
    }
}

fun merge(array : Array<Int>, startIndex: Int, midIndex : Int, endIndex: Int) {
    // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
    var f = startIndex // f의 최댓값은 midIndex

    // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
    var s = midIndex + 1 // s의 최댓값은 endIndex

    // Temporary 배열 그리고 이 배열을 순회할 인덱스 t
    val T : Array<Int> = Array(endIndex - startIndex + 1) { 0 }
    var t = 0

    while(f <= midIndex && s <= endIndex) {

        if(array[f] < array[s]) {
            T[t++] = array[f++]

        } else {
            T[t++] = array[s++]
        }
    }

    while(f <= midIndex) {
        T[t++] = array[f++]
    }

    while(s <= endIndex) {
        T[t++] = array[s++]
    }

    for(i : Int in 0..(T.size - 1)) {
        array[startIndex + i] = T[i]
    }
}