[백준] 28417 (스케이트보드)

#1 알고리즘

퀵 정렬 (Quick Sort)

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

 

#2 코드

#2-1 자바

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int highestScore = 0;
        int personCount = sc.nextInt();
        sc.nextLine();
        for(int i = 0; i < personCount; i++) {
            // 점수 배열 scores 만들기
            String[] testCase = sc.nextLine().trim().split(" ");
            int[] scores = new int[testCase.length];
            for(int j = 0; j < testCase.length; j++) {
                scores[j] = Integer.parseInt(testCase[j]);
            }
            
            int runScore = scores[0] < scores[1] ? scores[1] : scores[0];
            
            // scores[2] ~ score[6]을 오름차순으로 정렬
            quickSort(scores, 2, (scores.length - 1));
            int trickScore = scores[scores.length - 1] + scores[scores.length - 2]; // 제일 높은 점수 + 그 다음으로 높은 점수
            
            int totalScore = runScore + trickScore;
            if(highestScore < totalScore) {
                highestScore = totalScore;
            }  
        }
        
        System.out.println(Integer.toString(highestScore));
        
        sc.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(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;
    }
}

 

#2-2 코틀린

fun main() {
    var highestScore = 0
    val personCount = readln().trim().toInt()
    for(i : Int in 0..<personCount) {
        // 점수 배열 scores 만들기
        val testCase = readln().trim().split(" ")
        val scores : Array<Int> = Array(testCase.size) { 0 }
        for(j : Int in 0..<testCase.size) {
            scores[j] = testCase[j].toInt()
        }

        val runScore = if(scores[0] < scores[1]) { scores[1] } else { scores[0] }

        // scores[2] ~ score[6]을 오름차순으로 정렬
        quickSort(scores, 2, (scores.size - 1))
        val trickScore = scores[scores.size - 1] + scores[scores.size - 2] // 제일 높은 점수 + 그 다음으로 높은 점수

        val totalScore = runScore + trickScore
        if(highestScore < totalScore) {
            highestScore = totalScore
        }
    }

    println("${highestScore}")
}

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

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if(startIndex < endIndex) {
        val pivotIndex = partitionAroundPivot(array, startIndex, endIndex)
        quickSort(array, startIndex, (pivotIndex - 1))
        quickSort(array, pivotIndex, endIndex)
    }
}

// endIndex가 pivot(기준)의 역할 수행
fun partitionAroundPivot(array: Array<Int>, startIndex : Int, endIndex: Int) : Int {
    var endOfLower = startIndex - 1

    for (i: Int in startIndex..<endIndex) {
        if (array[i] <= array[endIndex]) {
            // array[endIndex]보다 lower인 값 저장할 공간 확보를 위해 endOfLower++
            endOfLower++

            // array[i]와 array[endOfLower]의 값 서로 교환
            val temp = array[endOfLower]
            array[endOfLower] = array[i]
            array[i] = temp
        }
    }

    // array[endOfLower] 바로 뒤에 array[endIndex] (= 기준) 값이 오게 하기 위해서 endOfLower++
    endOfLower++

    // array[endIndex]과 array[endOfLower]의 값 서로 교환
    val temp = array[endOfLower]
    array[endOfLower] = array[endIndex]
    array[endIndex] = temp

    return endOfLower
}