[Algorithm] 정수 내림차순으로 배치하기

문제 설명

함수 solution은 정수 n을 매개변수로 입력받습니다.

n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요.

예를들어 n이 118372면 873211을 리턴하면 됩니다.

 

문제 유형

• 숫자 자리값 구하기
• 내림차순 정렬

 

의사코드

1. 결과값을 저장할 변수(result)를 선언한다.
2. 우선순위 큐(pq)를 선언한다.
3. [반복문] num > 0 이면 반복한다.
   1. num을 10으로 나눈 나머지 값을 변수(remain)에 저장한다.
   2. remain을 우선순위 큐에 추가한다.
   3. num을 10으로 나누고 저장한다.
4. [반복문] !pq.empty() 이면 반복한다.
   1. pq의 첫번째 요소를 확인하여 변수(topNum)에 저장한다.
   2. result에 10을 곱하여 모든 자리수를 왼쪽으로 한칸 전진시킨다.
   3. result의 일의 자리에 topNum을 추가한다.
   4. pq의 첫번째 요소를 꺼낸다.
5. 결과값(result)를 반환한다.

 

코드 작성

long long solution(long long num) {
    long long result = 0;
    priority_queue<int> pq;
    
    while (num > 0)
    {
        int remain = num % 10;
        pq.push(remain);
        num /= 10;
    }
    
    while (!pq.empty())
    {
        int topNum = pq.top();
        result *= 10;
        result += topNum;
        pq.pop();
    }
    
    return result;
}