[Algorithm] 백준(BOJ) - 1427. 소트인사이드 (JAVA)

소트인사이드

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

Example

#1

입력
2143

출력
4321

#2

입력
999998999

출력
999999998

#3

입력
61423

출력
64321

#4

입력
500613009

출력
965310000

---

내가 작성한 코드

우선 지난 번에 Arrays.sort() 메소드를 이용하여 풀면 시간초과가, Collection.sort() 메소드를 이용하여 풀면 통과되었던 기억이 있어서 Collection.sort() 메소드를 이용하여 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] arr = br.readLine().split("");
        
        List<Integer> list = new ArrayList<>();
        for (String str : arr) {
            list.add(Integer.parseInt(str));
        }
        
        Collections.sort(list);
        Collections.reverse(list);
        
        for (int a : list) {
            sb.append(a);
        }
        
        System.out.println(Integer.parseInt(sb.toString()));
    }
}

다른 분들은 어떻게 풀었나 알아보니, 아래와 같은 풀이 방법들이 있었다.

• 카운팅 정렬을 이용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] counting = new int[10];
        String str = br.readLine();
        
        for (int i = 0; i < str.length(); i++) {
            counting[str.charAt(i) - '0']++;
        }
        
        for (int i = 9; i >= 0; i--) {
            while (counting[i]-- > 0) {
                System.out.print(i);
            }
        }
    }
}

• Arrays.sort() 메소드를 이용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        Arrays.sort(arr);
        for (int i = arr.length-1; i >= 0; i--) {
            System.out.print(arr[i]);
        }
    }
}

위 세 가지 풀이 방법의 성능은 어떻게 될까?

위부터 순서대로,

• 36445140 : Arrays.sort() 메소드를 이용한 풀이
• 36445068 : 카운팅 정렬을 이용한 풀이
• 36444848 : Collections.sort() 메소드를 이용한 풀이 (내 풀이)

로 속도는 내가 작성한 풀이가 근소하게 빠르지만, 메모리가 차지하는 양은 제일 큰 것을 확인할 수 있다.

시간 복잡도 뿐만 아니라, 공간 복잡도까지 생각해서 풀이할 수 있도록 다른 방식들을 많이 찾아보고 고심하여 풀어보면 좋을 것 같다.

더 많은 알고리즘 문제 풀이는 여기서 확인할 수 있다.