코틀린 코딩테스트 강좌, 내림차순으로 자릿수 정렬하기

문제 설명

주어진 정수 N의 각 자릿수를 내림차순으로 정렬하여 그 수를 재구성하라. 자릿수를 정렬한 후의 숫자를 반환하라. 단, 정수 N은 0 이상 2³¹-1 이하이다.

예를 들어:

• 입력: 118372 → 출력: 873211
• 입력: 2143 → 출력: 4321
• 입력: 0 → 출력: 0

해결 과정

1단계: 문제 이해하기

문제를 해결하기 위해 첫 번째로 할 일은 주어진 문제를 정확하게 이해하는 것입니다. 입력값은 정수 형태이며, 우리가 해야 할 일은 이 정수를 자릿수별로 분리한 후 내림차순으로 정렬하는 것입니다. 정렬이 완료된 자릿수를 다시 조합하여 정수 형태로 반환해야 합니다.

2단계: 각각의 자릿수 추출하기

정수를 문자열로 변환하여 각 자릿수를 쉽게 접근할 수 있습니다. 문자열의 각 문자는 원래 정수의 자릿수를 나타내며, 이를 이용해 자릿수를 추출할 수 있습니다.

3단계: 자릿수 정렬하기

자릿수를 정렬하기 위해 코틀린의 기본 제공 기능을 사용할 수 있습니다. sortedDescending() 함수를 이용하여 자릿수를 내림차순으로 정렬할 수 있습니다.

4단계: 정렬된 자릿수 조합하기

정렬된 자릿수를 이용해 최종 결과를 다시 정수로 변환하는 작업이 필요합니다. 각 자릿수를 이어붙여 하나의 문자열로 만든 후 이를 다시 정수로 변환하여 반환하면 됩니다.

5단계: 최종 코드 구현

fun solution(N: Int): Int {
    // 정수 N을 문자열로 변환
    val strN = N.toString()
    
    // 자릿수를 내림차순으로 정렬
    val sortedDigits = strN.toCharArray().sortedDescending()
    
    // 정렬된 자릿수를 다시 합쳐 하나의 문자열로 만들기
    val resultStr = sortedDigits.joinToString("")
    
    // 문자열을 정수로 변환하여 반환
    return resultStr.toInt()
}
            

예제 테스트

작성한 솔루션을 테스트하기 위해 각 테스트 케이스를 실행해보겠습니다.

fun main() {
    println(solution(118372)) // 873211
    println(solution(2143))   // 4321
    println(solution(0))      // 0
}
            

위 코드를 실행하면 예상한대로 각 정수가 내림차순으로 정렬되어 출력됩니다.

시간 복잡도 및 공간 복잡도

여기서 사용된 알고리즘의 시간 복잡도는 O(d log d)입니다. 여기서 d는 자릿수의 수입니다. 자릿수를 정렬해야 하므로 로그 시간의 복잡도가 생깁니다. 공간 복잡도는 O(d)로, 자릿수를 저장하기 위한 배열을 사용하였습니다.

결론

이번 강좌를 통해 알고리즘 문제 해결에 있어 코틀린의 강력한 기능과 간결한 문법을 활용하는 방법을 배웠습니다. 자릿수 정렬 문제는 다른 알고리즘 문제로 확장할 수 있는 좋은 출발점입니다. 더 많은 문제를 풀어보면서 다양한 알고리즘과 자료구조를 익히는 것이 중요합니다.

코딩테스트 준비에 많은 도움이 되길 바랍니다. 다음 강좌도 기대해 주세요!