자연수 N을 입력받아 자연수 안에서 각 자릿수를 내림차순으로 정렬하는 문제이다.
우선 각 자리수로 수를 나누어 크기 순으로 정렬한 뒤 다시 합치면 된다.
다음은 Java로 작성한 코드이다.
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class SortInside {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
//역전된 우선 순위 큐
PriorityQueue<Integer> solution = new PriorityQueue<Integer>(Collections.reverseOrder());
//한자리씩 떼어 우선순위 큐에 저장
int count=10;
while(num > 10) {
solution.add(num % (count));
num = num / (count);
}
solution.add(num);
//큰 순서대로 붙이기
int temp=0;
while(!solution.isEmpty()) {
temp *= 10;
temp += solution.poll();
}
System.out.println(temp);
}
}
num은 입력받는 자연수이다.
우선순위 큐를 이용하면, 답을 구해내기 정말 쉬워진다.
Java에서 우선순위 큐는 작은 수부터 out 된다. 하지만, Collections.reverseOrder()라는 속성을 적용시킨다면, 큰 수부터 out 시킬 수 있다.
num이 한자리수가 되기 전까지 계속하여 10으로 나머지 연산을 실행한다. 그렇다면 제일 끝자리의 수를 알아낼 수 있고 그 수를 우선순위 큐에 저장한다.
그 후, num을 10으로 나누어 끝자리를 떼어낸 수로 만들어 주며 진행한다.
한자리만 남게 되면, while loop를 종료한 뒤 남은 한자리의 수까지 우선순위 큐에 저장한다.
그렇다면, 우선순위 큐에는 큰 수부터 차례대로 out시킬 수 있게 된다.
큐에 요소가 남아있지 않을 때까지 계속해서 10을 곱하여 수를 더해나간다.
이렇게 원하는 답을 구할 수 있다.
