[Java]백준 10989번: 수 정렬하기 3

문제 url:
수 정렬하기 3

문제:

🤔 문제 알아보기

---

사실 해당 문제를 풀기 이전, 계수 정렬을 배운 터라, 시간 복잡도, 메모리 등을 가급적 고려하지 않고 풀 수 있었다.

먼저, 계수 정렬(counting sort)같은 경우 시간 복잡도가 O(N)으로 비교 정렬보다 빠르다. 하지만, 수의 범위(여기서는 10,000보다 작거나 같다고 했으니 0 ~ 10,000 까지) 크다면 메모리 낭비가 심하기 때문에 고려를 했어야 했다.

10,000까지 범위라서 얘매하지만 충분히 가능할 것이라고 판단하였다.
int형 4byte에 10,000까지니깐 40,000byte 배열의 크기만 약 그 정도로 파악해보았다.
메모리 접근 방법이 익숙지 않아서, 혹시 좋은 방법이 있다면 알려주셨으면 한다.

어쨋든, 해당 문제는 계수 정렬과 Arrays.sort()로 한번 풀어보도록 하겠다.

🐱‍👤 실제 코드(계수 정렬)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbd = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[10001]; // 수가 10000보다 작거나 같은 수라고 범위가 지정됐으니깐.

        for (int i = 0; i < N; i++) {
            arr[Integer.parseInt(br.readLine())]++;
        }

        for (int i = 0; i< arr.length; i++) {

            // 즉 arr[i]에는 해당 인덱스의 숫자가 개수만큼 들어있다.
            // i는 즉, 값을 의미하며  arr[i]에 있는 값은 i가 몇개 있는지를 의미한다.
            // arr[i]가 0이 될때까지 i를 출력. 즉 7이 4개 있으면 7777 출력
            while(arr[i]-- > 0) {
                sbd.append(i).append("\n");

            }
        }
        System.out.println(sbd);




    }
}

계수 정렬은 수의 범위가 정해졌으면, 고려할 수 있는 좋은 정렬 방법이다.
즉, 입력값을 받으면 arr 배열의 인덱스에 개수를 1씩 증가하는 방법으로
비교 없이 정렬을 나타낸 방법이다.

계수 정렬에 조금 더 알아보고 싶으면 아래 링크를 확인해라
[정렬] 계수 정렬(counting sort)에 대해 알아보자

🐱‍👤 실제 코드(Arrays.sort())

---

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbd = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];


        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        for(int val : arr) {
            sbd.append(val).append("\n");
        }
        System.out.println(sbd);



    }
}

Arrays.sort()로 쉽게 풀 수 있다.

Arrays.sort() 역시 조금 더 알아보고 싶으면 아래 링크를 확인
Arrays.sort()