[백준] 11650 (좌표 정렬하기)

#1 알고리즘

힙 정렬 (Heap Sort)

정렬 알고리즘은 여러 가지가 있다. 상황에 맞추어 가장 적절한 알고리즘을 골라야 하지만, 나는 알고리즘을 공부 중이므로 사용해 보지 않은 정렬 알고리즘 중에 아무거나 골라서 사용한다. 이 문제에 사용할 알고리즘은 힙 정렬(Heap Sort)이다. 해당 정렬을 11650번 문제 풀이를 위해 약간 변형해, 주어진 x값이 같으면, y값을 비교해서 대소를 구분한다.

 

#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 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][2];
        for(int i = 0; i < arrayLength; i++) {
            String[] stringElements = br.readLine().trim().split(" ");
            array[i][0] = Integer.parseInt(stringElements[0]);
            array[i][1] = Integer.parseInt(stringElements[1]);
        }
        
        br.close();
        
        HeapSort(array, 0, array.length - 1);
        
        for(int i = 0; i < array.length; i++) {
            bw.write(array[i][0] + " " + array[i][1] + "\n");
        }

        bw.flush();
        
        bw.close();		
    }

    private static void HeapSort(int[][] array, int startIndex, int endIndex) {
        int[][] slicedArray = new int[endIndex - startIndex + 1][2];
        for(int i = 0; i < slicedArray.length; i++) {
            slicedArray[i] = array[startIndex + i];
        }
        
        buildHeap(slicedArray);
        
        for(int maxIndex = (slicedArray.length - 1); maxIndex >= 1; maxIndex--) {
            int[] temp = slicedArray[0];
            slicedArray[0] = slicedArray[maxIndex];
            slicedArray[maxIndex] = temp;
            
            // maxIndex는 트리에서 제거된 취급이다. 따라서, maxIndex - 1까지 수선한다.
            heapify(slicedArray, 0, maxIndex - 1);
        }
        
        int[][] reversedArray = new int[slicedArray.length][2];
        for(int i = 0; i < reversedArray.length; i++) {
            reversedArray[i] = slicedArray[slicedArray.length - 1 - i];
        }
        
        for(int i = 0; i < reversedArray.length; i++) {
            array[startIndex + i] = reversedArray[i];
        }
    }

    private static void heapify(int[][] array, int rootIndex, int maxIndex) {
        int left = (rootIndex * 2) + 1;
        int right = (rootIndex * 2) + 2;
        int smaller = -1;
        
        // array[rootIndex]의 자식이 둘인 경우
        if(right <= maxIndex) {
            if(isSecondParameterGreaterThanFirst(array[left], array[right])) {
                smaller = left;
            } else {
                smaller = right;
            }
            
        // array[rootIndex]의 자식이 왼쪽 하나인 경우	
        } else if(left <= maxIndex){
            smaller = left;
            
        // array[rootIndex]의 자식이 없는 경우 (= 리프 노드)
        } else {
            return;
        }
        
        // 최소 힙이므로 array[rootIndex]가 더 작아야 한다
        if(isSecondParameterGreaterThanFirst(array[smaller], array[rootIndex])) {
            // 두 값의 위치 교환
            int[] temp = array[smaller];
            array[smaller] = array[rootIndex];
            array[rootIndex] = temp;
            
            // smaller를 rootIndex로 하는 heapify() 재귀적 수행
            heapify(array, smaller, maxIndex);
        }
        
    }

    private static boolean isSecondParameterGreaterThanFirst(int[] first, int[] second) {
        if(first[0] < second[0]) {
            return true;
            
        } else if(first[0] > second[0]) {
            return false;
            
        } else { // first[0] == second[0]
            
            if(first[1] < second[1]) {
                return true;
                
            } else if(first[1] > second[1]){
                return false;
            
            } else { // first[1] == second[1]
                return false;
            }
        }
    }

    // 알고리즘에서 직관적인 이해를 위해 매개 변수에 넣었던 maxIndex를 함수 내부로 이동시켰다.
    private static void buildHeap(int[][] array) {
        int maxIndex = array.length - 1;
        
        for(int i = (maxIndex / 2); i >= 0; i--) {
            heapify(array, i, maxIndex);
        }
    }
}

 

#2-1 코틀린

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 arrayLength : Int = br.readLine().trim().toInt()
    val array : Array<Array<Int>> = Array (arrayLength) { Array(2) { 0 } }
    for(i : Int in 0..(array.size - 1)) {
        val stringElements = br.readLine().trim().split(" ")
        array[i][0] = stringElements[0].toInt()
        array[i][1] = stringElements[1].toInt()
    }

    br.close()

    heapSort(array, 0, array.size - 1)

    for(i : Int in 0..(array.size - 1)) {
        bw.write("${array[i][0]} ${array[i][1]} \n")
    }
    bw.flush()

    bw.close()
}

fun heapSort(array : Array<Array<Int>>, startIndex : Int, endIndex : Int) {
    val slicedArray = array.sliceArray(startIndex..endIndex)

    buildHeap(slicedArray)

    for(maxIndex : Int in (slicedArray.size - 1) downTo 1) {
        val temp = slicedArray[0]
        slicedArray[0] = slicedArray[maxIndex]
        slicedArray[maxIndex] = temp

        // maxIndex는 트리에서 제거된 취급이다. 따라서, maxIndex - 1까지 수선한다.
        heapify(slicedArray, 0, maxIndex - 1)
    }

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

fun heapify(array : Array<Array<Int>>, rootIndex: Int, maxIndex: Int) {
    val left = (rootIndex * 2) + 1
    val right = (rootIndex * 2) + 2
    var smaller = -1

    // array[rootIndex]의 자식이 둘인 경우
    if(right <= maxIndex) {
        if(isSecondParameterGreaterThanFirst(array[left], array[right])) {
            smaller = left
        } else {
            smaller = right
        }

        // array[rootIndex]의 자식이 왼쪽 하나인 경우
    } else if(left <= maxIndex) {
        smaller = left

        // array[rootIndex]의 자식이 없는 경우 (= 리프 노드)
    } else {
        return
    }

    // 최소 힙이므로 array[rootIndex]가 더 작아야 한다
    if(isSecondParameterGreaterThanFirst(array[smaller], array[rootIndex])) {
        // 두 값의 위치 교환
        val temp = array[smaller]
        array[smaller] = array[rootIndex]
        array[rootIndex] = temp

        // smaller를 rootIndex로 하는 heapify() 재귀적 수행
        heapify(array, smaller, maxIndex)
    }
}

fun isSecondParameterGreaterThanFirst(first: Array<Int>, second: Array<Int>): Boolean {
    if (first[0] < second[0]) {
        return true

    } else if (first[0] > second[0]) {
        return false

    } else { // first[0] == second[0]
        if (first[1] < second[1]) {
            return true

        } else if (first[1] > second[1]) {
            return false

        } else { // first[1] == second[1]
            return false
        }
    }
}

fun buildHeap(array : Array<Array<Int>>) {
    val maxIndex = array.size - 1

    for(i : Int in (maxIndex / 2) downTo 0) {
        heapify(array, i, maxIndex)
    }
}