문제 설명
본 문제에서는 주어진 수들을 오름차순으로 정렬하는 알고리즘을 구현하는 것입니다. 정렬된 결과를 출력하기 전에, 입력으로 주어진 정수들을 읽어들이고, 중복된 정수는 제거한 뒤 정렬된 결과만을 출력합니다.
문제 입력
첫째 줄에 수의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)
둘째 줄에는 N개의 정수가 주어지며, 이 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같습니다.
문제 출력
정렬된 수를 한 줄에 하나씩 증가하는 순서로 출력합니다. 중복된 수는 한 번만 출력합니다.
문제 예시
입력:
5
5
5
3
2
1
출력:
1
2
3
5
문제 해결 과정
이 문제를 해결하기 위해서는 다음과 같은 단계를 따릅니다:
- 입력 받기: 사용자가 입력한 수의 개수 N과 N개의 정수를 받아들입니다.
- 중복 제거: 입력으로 들어온 정수들 중 중복된 수를 제거합니다.
- 정렬하기: 남은 정수들을 오름차순으로 정렬합니다.
- 출력하기: 정렬된 수들을 출력하는 함수를 구현합니다.
이 과정을 코틀린으로 구현할 때, 각 단계에 대한 코드 예제를 아래에 작성하겠습니다.
코드 구현
fun main() {
// 첫 번째 줄에서 수의 개수 N을 입력 받습니다.
val n = readLine()!!.toInt()
// 두 번째 줄에서 N개의 정수를 읽어옵니다.
val numbers = mutableSetOf() // 중복을 피하기 위해 Set 사용
// N개의 정수를 입력받고 중복 제거
for (i in 1..n) {
numbers.add(readLine()!!.toInt())
}
// List로 변환하여 정렬
val sortedNumbers = numbers.toList().sorted()
// 정렬된 결과 출력
for (num in sortedNumbers) {
println(num)
}
}
이 코드는 다음과 같이 작동합니다:
- 첫 줄에서 사용자로부터 수의 개수 N을 입력받습니다. 그 후 N번의 반복을 통해 정수를 입력받습니다.
- 각 정수는
mutableSetOf에 추가되어 중복이 자연스럽게 제거됩니다. - 이를
toList()메서드를 이용하여 List로 변환하고sorted()를 호출해 정렬합니다. - 마지막으로, 정렬된 결과를 출력합니다.
시간 복잡도 분석
이 문제의 시간 복잡도를 분석해보면:
- 정수를 읽어들이는 과정은 O(N)이며, 중복 확인을 위한 Set 사용은 평균적으로 O(1)입니다.
- Set의 모든 요소를 List로 변환하고 정렬하는 과정은 O(M log M)입니다. 여기서 M은 고유한 수의 개수입니다.
- 결과적으로, 시간 복잡도는 O(N + M log M)으로 평가할 수 있습니다.
결론
이번 강좌에서는 수 정렬하기 문제를 통해 코틀린의 기본적인 자료 구조와 정렬 알고리즘을 복습했습니다. 코틀린은 특히 Set과 List의 활용에 강점을 가지므로, 이 두 가지를 효율적으로 사용하면 많은 문제를 간단하게 해결할 수 있습니다. 다음 강좌에서는 좀 더 복잡한 알고리즘 문제를 다룰 예정이니 많은 기대 부탁드립니다.