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

#1 알고리즘

#1-1

11650 - 좌표 정렬하기

해당 문제의 코드를 그대로 사용하되,문제의 조건에 맞추어 isSecondParameterGreaterThanFirst()의 내부 로직을 변경했다.

 

#1-2

병합 정렬 (Merge Sort)

또, 이전 문제(11650번 문제)에서 사용했던 힙 정렬 대신 병합 정렬을 이용해봤다.

 

#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();
        
        mergeSort(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();		
    }

    public 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);
        }
    }

    public 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
        
        // 'T'emporary 배열 그리고 이 배열을 순회할 인덱스 t
        int[][] T = new int[endIndex - startIndex + 1][2];
        int t = 0;
        
        while(f <= midIndex && s <= endIndex) {
            
            if(isSecondParameterGreaterThanFirst(array[f], array[s])) {
                T[t++] = array[f++];
                
            } else {
                T[t++] = array[s++];
                
            }
        }
        
        // f의 영역이 남았다면 비워준다
        while(f <= midIndex) {
            T[t++] = array[f++];
        }
        
        // s의 영역이 남았다면 비워준다
        while(s <= endIndex) {
            T[t++] = array[s++];
        }
        
        for(int i = 0; i < T.length; i++) {
            array[startIndex + i] = T[i];
        }
    }

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

 

#2-2 코틀린

package exam11651

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()

    mergeSort(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 mergeSort(array: 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<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

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

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

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

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

    // f의 영역이 남았다면 비워준다
    while(f <= midIndex) {
        T[t++] = array[f++]
    }

    // s의 영역이 남았다면 비워준다
    while(s <= endIndex) {
        T[t++] = array[s++]
    }

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

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

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

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

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

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

 

#3 실패한 코드 - 시간 초과 - 자바

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();
        
        quickSort(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();		
    }

    public static void quickSort(int[][] array, int startIndex, int endIndex) {
        // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
        if(startIndex < endIndex) {
            int pivotIndex = partitionAroundPivot(array, startIndex, endIndex);
            quickSort(array, startIndex, (pivotIndex - 1));
            quickSort(array, pivotIndex, endIndex);
        }
    }

    // endIndex가 pivot(기준)의 역할 수행
    private static int partitionAroundPivot(int[][] array, int startIndex, int endIndex) {
        int endOfLower = startIndex - 1;
        
        for(int i = startIndex; i < endIndex; i++) {
            if(isSecondParameterGreaterOrEqual(array[i], array[endIndex])) {
                // array[endIndex]보다 lower인 값 저장할 공간 확보를 위해 endOfLower++
                endOfLower++;
                
                // array[i]와 array[endOfLower]의 값 서로 교환
                int[] temp = array[endOfLower];
                array[endOfLower] = array[i];
                array[i] = temp;
            }
        }
        
        // array[endOfLower] 바로 뒤에 array[endIndex] (= 기준) 값이 오게 하기 위해서 endOfLower++
        endOfLower++;
        
        // array[endIndex]과 array[endOfLower]의 값 서로 교환
        int[] temp = array[endOfLower];
        array[endOfLower] = array[endIndex];
        array[endIndex] = temp;
        
        return endOfLower;
    }

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

퀵 정렬을 이용해봤다. 퀵 정렬 알고리즘에 맞춰 isSecondParameterGreaterThanFirst()를 isSecondParameterGreaterOrEqual()로 수정했고, 수정된 이름에 걸맞게 내부 로직을 손봤다. 하지만, 퀵 정렬은 평균 시간은 빠르지만, 최악의 경우엔 느린 정렬 알고리즘이다.