[BOJ 1427] 소트인사이드 - [정렬 / 문자열]

[BOJ 1427] 소트인사이드 - [정렬 / 문자열]

문제 링크

https://www.acmicpc.net/problem/1427

문제 요약

주어진 자연수 $N$의 각 자릿수를 내림차순으로 정렬하여 출력하는 문제입니다.

접근 방법

• 자료구조: std::string (문자열)
• 알고리즘: 정렬 (Sorting)
• 핵심 아이디어: - 입력값 $N$이 최대 10억이므로 각 자릿수를 분리하기 위해 string으로 입력받습니다.
  • 문자열의 각 문자는 결국 하나의 숫자를 의미하므로, algorithm 헤더의 sort 함수를 이용해 문자 단위로 정렬합니다.
  • 내림차순 정렬을 위해 greater<char>() 비교 함수를 사용합니다.

풀이 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    // 빠른 입출력을 위한 설정
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string n;
    // 1. 숫자를 문자열 형태로 입력받음
    if (!(cin >> n)) return 0;

    // 2. 문자열 내의 각 자릿수(문자)를 내림차순 정렬
    // sort(시작점, 끝점, 비교기준)
    sort(n.begin(), n.end(), greater<char>());

    // 3. 정렬된 결과 출력
    cout << n << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(L \log L)$ (여기서 $L$은 숫자의 길이를 의미하며, 최대 10이므로 매우 빠름)
• 공간 복잡도: $O(L)$ (입력받은 문자열을 저장하는 공간)

실행 결과

• 메모리: 약 2024 KB
• 시간: 0 ms

핵심 포인트

1. 숫자를 int나 long long으로 받아 %10, /10 연산으로 자릿수를 분리할 수도 있지만, string을 활용하면 코드가 훨씬 간결해집니다.
2. C++ STL의 sort는 기본적으로 오름차순이므로, 내림차순을 위해 greater<Type>()을 사용하거나 커스텀 비교 함수를 정의해야 합니다.

예제 확인

• 예제 1 (2143): 정렬 후 '4321' 출력 확인.
• 예제 4 (500613009): 정렬 후 '965310000' 출력 확인.