[백준] 27522 (카트라이더: 드리프트)

#1 알고리즘

삽입 정렬 (Insertion Sort)

정렬 알고리즘은 여러 가지가 있다. 상황에 맞추어 가장 적절한 알고리즘을 골라야 하지만, 나는 알고리즘을 공부 중이므로 사용해 보지 않은 정렬 알고리즘 중에 아무거나 골라서 사용한다. 이 문제에 사용할 알고리즘은 삽입 정렬(Insert Sort)이다. 문제에 조건에 맞춰 삽입 정렬 알고리즘을 약간 수정했다. 삽입 정렬의 핵심 원리는 그대로지만, 시간 저장용 배열 그리고 팀 저장용 배열 총 배열 2개를 매개변수로 가진다.
 

#2 코드

#2-1 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int[] scores = {10, 8, 6, 5, 4, 3, 2, 1, 0};
        int[] times = new int[8];
        char[] teams = new char[8];
        
        for(int i = 0; i < 8; i++) {
            String testCase = sc.nextLine().trim();
            times[i] = Integer.parseInt(testCase.replaceAll("[^0-9]", ""));
            teams[i] = testCase.charAt(testCase.length() - 1);
        }
        
        sc.close();
        
        // times 내 원소를 이동시킬때, teams에서도 똑같이 이동시킨다.
        insertSort(times, teams, 0, 7);

        // times는 이제부터 필요 없다
        
        int totalRedScore = 0;
        int totalBlueScore = 0;

       for(int i = 0; i < 8; i++) {
            if(teams[i] == 'R') {
                totalRedScore += scores[i];
            } else {
                totalBlueScore += scores[i];
            }
        }

        if(totalBlueScore < totalRedScore) {
            System.out.println("Red");
        } else {
            System.out.println("Blue");
        }
    }
    
    private static void insertSort(int[] array1, char[] array2, int startIndex, int endIndex) {

        for(int maxIndex = (startIndex + 1); maxIndex <= endIndex; maxIndex++) {
            // array1[maxIndex]가 최댓값인 경우
            if(array1[maxIndex - 1] <= array1[maxIndex]) {
                continue;

            // array1[maxIndex]가 최댓값이 아닌 경우
            } else {
                insertion(array1, array2, startIndex, maxIndex);
            }
        }
    }

    private static void insertion(int[] array1, char[] array2, int startIndex, int insertIndex) {

        // 삽입 위치 찾기
        int insertionDestination = -1;
        for(int i = startIndex; i < insertIndex; i++) {
            if(array1[insertIndex] <= array1[i]) {
                insertionDestination = i;
                break;
            }
        }

        // 삽입 위치에 따른 array1의 인덱스 조정
        int temp1 = array1[insertIndex];
        for(int i = (insertIndex - 1); i >= insertionDestination; i--) {
            array1[i + 1] = array1[i];
        }
        array1[insertionDestination] = temp1;

        // 삽입 위치에 따른 array2의 인덱스 조정
        char temp2 = array2[insertIndex];
        for(int i = (insertIndex - 1); i >= insertionDestination; i--) {
            array2[i + 1] = array2[i];
        }
        array2[insertionDestination] = temp2;
    }
}

 

#2-2 코틀린

fun main() {
    val scores : Array<Int> = arrayOf(10, 8, 6, 5, 4, 3, 2, 1, 0)
    val times : Array<Int> = Array(8) { 0 }
    val teams : Array<Char> = Array(8) { ' ' }

    for(i : Int in 0..7) {
        val testCase = readln()!!.trim()
        times[i] = testCase.replace(Regex("[^0-9]"), "").toInt()
        teams[i] = testCase[testCase.length - 1]
    }

    // times 내 원소를 이동시킬때, teams에서도 똑같이 이동시킨다.
    insertSort(times, teams, 0, 7)

    // times는 이제부터 필요 없다

    var totalRedScore = 0
    var totalBlueScore = 0

    for(i : Int in 0..7) {
        if(teams[i] == 'R') {
            totalRedScore += scores[i]
        } else {
            totalBlueScore += scores[i]
        }
    }

    if(totalBlueScore < totalRedScore) {
        println("Red")
    } else {
        println("Blue")
    }
}

fun insertSort(array1: Array<Int>, array2 : Array<Char>, startIndex : Int, endIndex : Int) {

    for(maxIndex : Int in (startIndex + 1)..endIndex) {
        // array1[maxIndex]가 최댓값인 경우
        if(array1[maxIndex - 1] <= array1[maxIndex]) {
            continue

            // array1[maxIndex]가 최댓값이 아닌 경우
        } else {
            insertion(array1, array2, startIndex, maxIndex)
        }
    }
}

fun insertion(array1 : Array<Int>, array2 : Array<Char>, startIndex : Int, insertIndex: Int) {

    // 삽입 위치 찾기
    var insertionDestination = -1
    for(i : Int in startIndex..<insertIndex) {
        if(array1[insertIndex] <= array1[i]) {
            insertionDestination = i
            break
        }
    }

    // 삽입 위치에 따른 array1의 인덱스 조정
    val temp1 = array1[insertIndex]
    for(i : Int in (insertIndex - 1) downTo insertionDestination) {
        array1[i + 1] = array1[i]
    }
    array1[insertionDestination] = temp1

    // 삽입 위치에 따른 array2의 인덱스 조정
    val temp2 = array2[insertIndex]
    for(i : Int in (insertIndex - 1) downTo insertionDestination) {
        array2[i + 1] = array2[i]
    }
    array2[insertionDestination] = temp2
}