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

1. 문제 정의

이번 문제의 목표는 주어진 숫자를 내림차순으로 정렬하여, 최대한 큰 수를 만드는 것입니다. 입력으로 주어진 숫자는 정수이며, 우리가 해야 할 일은 이 숫자의 자릿수를 이용하여 제일 큰 수를 반환하는 것입니다.

예제 입력/출력

• Input: 2183
• Output: 8321

2. 문제 접근 방법

이 문제는 각 자릿수의 개별 숫자를 추출한 후, 이를 내림차순으로 정렬하는 과정을 포함합니다. Python에서는 리스트의 sort() 메서드를 활용하여 손쉽게 이러한 정렬 작업을 수행할 수 있습니다. 구체적인 절차는 다음과 같습니다:

1. 정수를 문자열로 변환한다.
2. 문자열을 각 숫자(문자)로 분리하여 리스트를 만든다.
3. 리스트를 내림차순으로 정렬한다.
4. 정렬된 리스트를 다시 문자열로 합쳐 정수로 변환하여 반환한다.

3. 알고리즘 구현

이제 위의 접근 방법을 바탕으로 Python 코드로 문제를 해결해 보겠습니다.

def sort_digits_descending(n):
    # 1단계: 정수를 문자열로 변환
    str_n = str(n)
    
    # 2단계: 문자열을 리스트로 변환
    digits = list(str_n)
    
    # 3단계: 리스트를 내림차순으로 정렬
    digits.sort(reverse=True)
    
    # 4단계: 정렬된 리스트를 문자열로 합치고 정수로 변환
    sorted_n = int(''.join(digits))
    
    return sorted_n

4. 코드 설명

위 함수 sort_digits_descending는 매개변수 n을 받아서 전체 과정을 수행합니다. 각 단계는 다음과 같이 작동합니다:

• 문자열 변환: str(n)을 통해 정수를 문자열로 변환합니다.
• 리스트 변환: list(str_n)를 통해 문자열의 각 문자(숫자)를 리스트로 변환합니다.
• 정렬: sort(reverse=True)를 사용하여 리스트를 내림차순으로 정렬합니다.
• 합치기: "".join(digits)를 사용하여 리스트를 다시 문자열로 합쳐서, int()로 정수로 변환하여 반환합니다.

5. 테스트 케이스

우리의 기능이 제대로 작동하는지 확인하기 위해 여러 가지 테스트 케이스를 사용해 봅시다.

print(sort_digits_descending(2183)) # 8321
print(sort_digits_descending(1450)) # 5410
print(sort_digits_descending(9876543210)) # 9876543210
print(sort_digits_descending(0)) # 0
print(sort_digits_descending(1001)) # 1100

6. 결과 분석

각 테스트 케이스의 결과를 확인한 결과, 모든 경우에서 기대한 출력이 반환되었습니다. 함수는 매우 간단하게 구현되었으며, Python의 기본 기능을 사용하여 효율적으로 해결되었습니다.

7. 최적화 및 고려 사항

위에서 작성한 코드는 각 자릿수를 정렬하는 데 O(m log m) 시간 복잡도가 소요됩니다. 여기서 m은 입력 정수의 자릿수 수입니다. 정수의 최대 자릿수가 10으로 한정되기 때문에 성능상의 문제는 없지만, 효율성을 고려하여 더 큰 수에서도 유효하게 만들거나 복잡도를 줄일 필요가 있을 수 있습니다.

8. 정리

우리는 주어진 정수를 내림차순으로 정렬하여 최대한 큰 값을 만드는 알고리즘을 구현했습니다. 이 과정에서 Python의 리스트 메서드와 문자열 조작 기능을 사용하여 간단하게 해결할 수 있었습니다. 향후 추가적인 최적화와 다른 접근 방식을 고려하기 바랍니다. 이를 통해 코딩 테스트에서 더 뛰어난 문제 해결 능력을 기를 수 있습니다.