[프로그래머스] 정수 내림차순으로 배치하기 (Lv.1)

---

문제 링크

---

프로그래머스 - 정수 내림차순으로 배치하기

문제 설명

---

함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은순으로 정렬한 새로운 수를 리턴해주세요. 예를들어 n이 118372이면 873211을 리턴하면 됩니다.

제한사항

• n은 1이상 8,000,000,000 이하인 자연수입니다.

내 풀이

---

to_string()으로 숫자를 문자열로 변환한 뒤, 문자 단위로 내림차순 정렬한다. 문자 비교 시 '9' > '8' > ... > '0'이 성립하므로 커스텀 비교 함수 없이 a > b 조건만으로 자릿수 내림차순 정렬이 가능하다. 정렬 후 stoll()로 다시 숫자로 변환해 반환한다.

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

using namespace std;

long long solution(long long n) {
    long long answer = 0;
    string numbers = to_string(n);
    
    sort(numbers.begin(), numbers.end(), [](char a, char b) {
        return a > b;
    });
    
    answer = stoll(numbers);
    
    return answer;
}

시간복잡도 분석

---

• to_string(n): O(D), D = 자릿수 (n ≤ 8,000,000,000이므로 최대 10자리)
• sort: O(D log D), D ≤ 10
• stoll: O(D)
• 전체: O(D log D) ≈ O(1) (D가 최대 10으로 고정이므로 사실상 상수)

오답노트

---

처음에 stoi밖에 생각이 나지 않아 stoi로 numbers를 int형으로 캐스팅하고 long long 타입으로 캐스팅 하려 했다. 애초에 numbers의 길이가 int형에 담길 수 없어 오류가 발생했다.
그래서 혹시 하고 stoi의 i가 int니까 longlong을 줄여 ll로 바꾸면 되지 않을까 했더니 됐다.ㅋㅋ

후기

---

사람이 생각하는게 어쩌면 거기서 거기인 것 같기도 하다.

• algorithm
• codingtest
• sort