코틀린 코딩테스트 강좌, 022 수 정렬하기 3

문제 설명

이 문제는 주어진 수열을 정렬하는 알고리즘 문제입니다. 구체적으로,
N개의 정수를 입력받아 이 수들을 오름차순으로 정렬한 뒤
각 정수를 한 줄씩 출력하는 프로그램을 작성해야 합니다.

입력 형식

첫 번째 줄에 정수 N (1 ≤ N ≤ 1,000,000)이 주어집니다.
두 번째 줄에는 N개의 정수가 주어지며, 각각의 정수는
-1,000,000,000 이상
1,000,000,000 이하입니다.

출력 형식

입력 받은 정수를 오름차순으로 정렬하여 각 정수를 한 줄에 하나씩
출력합니다.

문제 접근법

이 문제를 해결하기 위해서는 배열을 정렬하는 알고리즘을 사용할 수 있습니다.
코틀린에서는 기본적으로 배열 정렬을 위한 강력한 라이브러리 함수가 제공되고 있습니다.
그러나 수의 크기가 크기 때문에 시간 복잡도에 유의해야 합니다.
최적의 성능을 위해 특별한 정렬 알고리즘을 적용해야 합니다.

알고리즘 선택

주어진 문제의 입력 크기가 1,000,000까지 가능하므로,
O(N log N) 시간 복잡도를 갖는 퀵소트(quick sort) 또는
합병 정렬(merge sort)과 같은 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.
또한 코틀린의 경우, 표준 라이브러리의 sort() 메서드를 활용하여
손쉽게 정렬할 수 있습니다.

코드 구현

아래는 코틀린을 이용한 문제 해결 코드입니다:


fun main() {
    val n = readLine()!!.toInt()  // 첫 번째 줄에서 N 입력
    val numbers = IntArray(n)      // 정수 배열 생성

    for (i in 0 until n) {
        numbers[i] = readLine()!!.toInt()  // 다음 N개의 정수 입력
    }

    numbers.sort()  // 정렬 수행

    numbers.forEach { println(it) }  // 정렬된 수 출력
}

코드 설명

1. readLine()!!.toInt()를 이용해 표준 입력으로부터
정수를 읽어옵니다. 첫 번째 줄에서 N의 값을 읽고,
후속 N개의 정수를 모두 배열 numbers에 저장합니다.

2. numbers.sort() 메서드를 사용하여
배열을 오름차순으로 정렬합니다. 이 메서드는
내부적으로 효율적인 정렬 알고리즘을 사용합니다.

3. 마지막으로, 정렬된 수들을 forEach를 통해
한 줄씩 출력합니다.

결과 예시

아래는 이 프로그램을 실행한 후의 예시 입력 및 출력입니다:

입력:

출력:

메모리 및 시간 복잡도

이 알고리즘은 O(N log N)의 시간 복잡도를 가집니다. 이는
입력 배열의 크기에 비례하여 로그 단계로 분할하여 정렬하기 때문입니다.
메모리 사용량은 배열을 저장하기 위해 O(N)만큼 필요합니다.

문제 해결 과정 정리

입력으로 주어진 모든 수를 배열에 저장한다.
배열을 오름차순으로 정렬한다.
정렬된 결과를 출력한다.

마무리

이번 강좌에서는 코틀린을 이용하여 수를 정렬하는
방법에 대해 배웠습니다. 체계적인 접근법을 통해
알고리즘 문제를 해결하는 방법을 익히고,
다양한 입력과 조건에서도 올바른 결과를 도출할 수
있도록 연습해야 합니다.

앞으로도 다양한 알고리즘 문제를 통해 실력을
키워보세요!