[백준] 1181 (단어 정렬)

#1 알고리즘

#1-1

선택 정렬 (Selection Sort)

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

 

#1-2

 

#2 코드

#2-1 자바

import java.util.Scanner;

public class Main {
    private static String[] array;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int arrayLength = sc.nextInt();
        sc.nextLine(); // 입력 버퍼의 첫째 줄 비워내기

        array = new String[arrayLength];

        for (int i = 0; i < array.length; i++) {
            array[i] = sc.nextLine().trim();
        }
        
        sc.close();
        
        selectionSortForExam1181(array, 0, array.length - 1);

        for(int i = 0; i < array.length; i++) {
            if(!array[i].equals("")) {
                System.out.println(array[i]);
            }
        }
    }

    private static void selectionSortForExam1181(String[] array, int startIndex, int endIndex) {

        for(int maxIndex = endIndex; startIndex < maxIndex; maxIndex--) {
            
            // 배열을 순회하며 가장 값이 큰 원소의 index를 구한다
            int indexOfLargest = 0;
            for(int i = 1; i <= maxIndex; i++) {
                if(isSecondParameterGreaterThanFirst(array[indexOfLargest], array[i], i)) {
                    indexOfLargest = i;
                }
            }
            
            // 가장 값이 컸던 원소와 맨 끝 index 원소의 값을 서로 교환한다
            String temp = array[maxIndex];
            array[maxIndex] = array[indexOfLargest];
            array[indexOfLargest] = temp;
        }
    }

    private static boolean isSecondParameterGreaterThanFirst(String s1, String s2, int indexOfS2) {
        
        // 길이가 다른 경우
        if(s1.length() < s2.length()) {
            return true;
        } else if(s1.length() > s2.length()) {
            return false;
        }
        
        // 길이가 같은 경우: 같은 문자열인지 확인
        if(s1.equals(s2)) {
            array[indexOfS2] = "";
            return false;
        }
        
        // 길이는 같지만, 같은 글자는 아닌 경우: 한 글자씩 유니코드값 비교
        for (int i = 0; i < s1.length(); i++) {
            int unicodeGap = s2.codePointAt(i) - s1.codePointAt(i);

            if (unicodeGap > 0) {
                return true;
                
            } else if (unicodeGap < 0) {
                return false;

            } else {
                continue; // 위에서 이미 s1과 s2가 같은 경우를 한번 걸렀기 때문에, 이 for문 내에서 반드시 우열이 가려진다
            }
        }
        
        return false; // 여기까지 올 일은 없다. 컴파일러가 난리쳐서 어쩔 수 없이 넣었다.
    }
}

코틀린 코드과 달리, 시간 초과가 뜰 때도 있고 아닐 때도 있다. 선택 정렬보다 더 높은 성능의 정렬를 사용할 필요가 있다. 추후 리팩토링하겠다.

 

#2-2 코틀린

lateinit var array: Array<String>

fun main() {
    val arrayLength = readln()!!.trim().toInt()
    array = Array(arrayLength) { "" }

    for(i : Int in 0..(array.size - 1)) {
        array[i] = readln()!!.trim()
    }

    selectionSortForExam1181(array, 0 , (array.size - 1))
    
    for(i : Int in 0..(array.size - 1)) {
        if(array[i] != "") {
            println(array[i])
        }
    }
}

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

    for(maxIndex : Int in endIndex downTo (startIndex + 1)) {

        // 배열을 순회하며 가장 값이 큰 원소의 index를 구한다
        var indexOfLargest = startIndex;
        for(i : Int in 1..maxIndex) {
            if(isSecondParameterGreaterThanFirst(array[indexOfLargest], array[i], i)) {
                indexOfLargest = i
            }
        }

        // 가장 값이 컸던 원소와 맨 끝 index 원소의 값을 서로 교환한다
        val temp = array[maxIndex]
        array[maxIndex] = array[indexOfLargest]
        array[indexOfLargest] = temp
    }
}

fun isSecondParameterGreaterThanFirst(s1: String, s2: String, indexOfS2: Int): Boolean {

    // 길이가 다른 경우
    if(s1.length < s2.length) {
        return true
    } else if(s1.length > s2.length) {
        return false
    }

    // 길이가 같은 경우: 같은 문자열인지 확인
    if(s1 == s2) {
        array[indexOfS2] = ""
        return false
    }

    // 길이는 같지만, 같은 글자는 아닌 경우: 한 글자씩 유니코드값 비교
    for(i : Int in 0..(s1.length - 1)) {
        val unicodeGap = s2.codePointAt(i) - s1.codePointAt(i)

        if(unicodeGap > 0) {
            return true

        } else if(unicodeGap < 0) {
            return false

        } else {
            continue // 위에서 이미 s1과 s2가 같은 경우를 한번 걸렀기 때문에, 이 for문 내에서 반드시 우열이 가려진다
        }
    }

    return false // 여기까지 올 일은 없다. 컴파일러가 난리쳐서 어쩔 수 없이 넣었다.
}