문제
주어진 수 N의 각 자릿수를 내림차순으로 정렬하여 출력하는 문제다. 예를 들어 2143이 입력되면 4321을 출력한다.
입력
- 첫째 줄: 정렬할 수 N (1 이상 10^9 이하)
출력
N의 각 자릿수를 내림차순으로 정렬한 결과를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2143 | 4321 |
999998999 | 999999998 |
풀이
입력을 문자열로 받아 각 문자를 정수로 변환한 뒤 오름차순 정렬 후 역순으로 출력하여 내림차순을 구현한다.
- 입력을 문자열
str로 읽는다. split("")으로 각 자릿수 문자를 분리하고int[]배열로 변환한다.Arrays.sort로 오름차순 정렬한다.- 배열 끝에서 시작으로 순서대로 출력하면 내림차순 결과를 얻는다.
핵심 아이디어: N이 최대 10^9이므로 int 범위를 초과할 수 있어 문자열로 입력받는 것이 안전하다. 오름차순 정렬 후 역순 출력을 이용하면 별도의 내림차순 비교자 없이 간단하게 구현할 수 있다.
코드
package com.ssafy.an.day049;
import java.util.Arrays;
import java.util.Scanner;
public class Day03BOJ1427소트인사이드 { // 1427
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String[] strNum = str.split("");
int[] num = new int[str.length()];
for (int i = 0; i < num.length; i++) {
num[i] = Integer.parseInt(strNum[i]);
}
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
System.out.print(num[num.length - 1 - i]);
}
sc.close();
}
}복잡도
- 시간: O(D log D) — D는 자릿수 개수 (최대 10), 사실상 O(1)에 가까움
- 공간: O(D) — 자릿수 배열 저장