코틀린 코딩테스트 강좌, 줄 세우기

문제 설명

일련의 학생들이 키에 따라서 줄을 서야 합니다. 학생들은 각자의 키를 가지고 있으며, 이 키의 기준에 따라 줄이 세워져야 합니다. 여러분은 학생들의 키 정보가 주어질 때, 이들을 키 순서대로 정렬하여 출력하는 프로그램을 작성해야 합니다.

입력 형식

• 첫 번째 줄: 학생의 수 N (1 ≤ N ≤ 100,000)
• 다음 N개의 줄: 각 학생의 키 H (1 ≤ H ≤ 2,000)

출력 형식

키가 작은 순서대로 학생들의 키를 한 줄에 하나씩 출력합니다.

예제 입력

        5
        140
        120
        150
        130
        110
        

예제 출력

        110
        120
        130
        140
        150
        

문제 해결 전략

이 문제는 학생들의 키를 정렬하는 문제로, 정렬 알고리즘을 통해 해결할 수 있습니다. 힌트로는 코틀린의 sort() 함수 또는 sorted() 함수를 활용하여 문제를 해결할 수 있습니다. 또한, 다양한 정렬 알고리즘의 시간 복잡도를 고려하여 최적의 방법을 선택해야 합니다.

단계 1: 입력 데이터 수집

학생 수와 각 학생의 키를 입력 받기 위해 표준 입력을 활용합니다. 코틀린은 간결한 코드 작성을 지원하므로, 이를 효율적으로 작성할 수 있습니다.

단계 2: 데이터 정렬

정렬 방법으로는 기본적으로 sort() 함수가 가장 쉽고 간편하게 적용됩니다. 이 함수는 내부적으로 Timsort 알고리즘을 사용하여 평균적으로 O(N log N)의 성능을 가지고 있습니다. 아래의 코드에서는 이 함수를 사용하여 학생들의 키를 정렬하는 방법을 설명합니다.

단계 3: 결과 출력

정렬된 결과를 한 줄에 하나씩 출력하는 과정을 거칩니다. 이는 코틀린의 반복문을 통해 간단히 구현할 수 있습니다.

코틀린 코드 구현

아래의 코드는 위에서 설명한 단계들을 기반으로 한 코틀린 프로그램의 코드입니다.

fun main() {
    val n = readLine()!!.toInt()  // 첫 번째 줄 학생 수 입력
    val heights = mutableListOf()  // 학생들의 키를 저장할 리스트

    // 키 입력 받기
    for (i in 1..n) {
        heights.add(readLine()!!.toInt())
    }

    // 키 정렬
    heights.sort()

    // 정렬된 결과 출력
    heights.forEach { height -> 
        println(height) 
    }
}
        

코드 설명

• readLine()!!.toInt(): 표준 입력에서 값을 읽어 정수형으로 변환합니다.
• mutableListOf(): 가변 리스트를 생성하여 학생의 키를 저장합니다.
• heights.sort(): 리스트를 정렬합니다.
• heights.forEach(): 정렬된 결과를 출력하는 반복문입니다.

결과 및 성능 분석

이 코드의 시간 복잡도는 O(N log N)이며, 이는 대규모 학생 수에 대해서도 효율적으로 처리할 수 있습니다. 또한 코드의 가독성이 높아 유지보수가 용이하다는 장점이 있습니다.

테스트 케이스

다양한 입력에 대한 테스트를 통해 프로그램의 안정성을 확인할 수 있습니다. 예를 들어, 동일한 키를 가진 학생의 경우나 역순으로 정렬된 경우 등의 다양한 테스트 케이스를 추가적으로 고려해야 합니다.

마무리

이번 강좌에서는 코틀린을 이용한 줄 세우기 문제를 해결하는 방법을 살펴보았습니다. 입력 처리, 데이터 정렬, 결과 출력의 과정을 통해 알고리즘 문제 해결 능력을 한층 더 발전시킬 수 있는 기회가 되었으면 합니다. 다음 강좌에서는 더욱 난이도 높은 문제를 다룰 예정입니다.