(Java) 백준 10989번 - 수 정렬하기 3

https://www.acmicpc.net/problem/10989

문제

> N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
> 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 
> 둘째 줄부터 N개의 줄에는 수가 주어진다. 
> 이 수는 10,000보다 작거나 같은 자연수이다.

접근

1. Arrays.sort를 사용하여 정렬한다.
2. 카운팅 정렬을 사용한다.

문제해결

> 1)
> N을 입력받고 N을 크기로 가지는 정수형 배열을 만든다.
> 수를 입력받아 저장하고 Arrays.sort로 정렬해준다.
> 스트링빌더를 사용해 정렬된값을 한번에 모아서 출력해준다.

> 2)
> 입력으로 들어 올 수 있는 수는 1 <= x <= 10,000이다.
> 카운팅 정렬을 사용하기 위해 int형 배열을 크기 10,001로 선언하여 입력으로 들어온 각 숫자의 입력횟수를 저장한다.
> 입력이 끝나면 값이 있는 인덱스들 중 작은 것부터 순서대로 값이 0이 될 때까지 반복해 출력한다.

코드 - 1

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main
{
    //10989번 수 정렬하기 3
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];

        for(int i = 0; i < N; i++) num[i] = Integer.parseInt(br.readLine());
        Arrays.sort(num);
        
        StringBuilder sb = new StringBuilder();
        for(int a : num) sb.append(a).append('\n');
        
        System.out.print(sb);
    }
}

코드 - 2

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[10_001];

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

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < num.length; i++)
        {
            if(num[i] == 0) continue;
            while(num[i] -- > 0) sb.append(i).append('\n');
        }
        System.out.print(sb);
    }
}

후기

메모리에 대해 깊게 생각해 볼 수 있는 좋은 문제였다. 뭔가 뾰족한 방법이 생각안나고 관성적으로 "그냥 sort 쓰면 되는거 아닌가?" 로 풀었는데 풀고 더 좋은 풀이가 있는지 GPT에게 물어보니 카운팅 정렬을 쓰라고 한다.
1번 방법으로 N크기만큼 만들면 최악의 경우엔 int(10,000,000) 배열이 생긴다. int형은 하나당 4byte를 차지하는데 이게 10,000,000이면 40,000,000이고 이를 MB로 변환하면 약 40MB가 나온다. 즉 문제의 8MB보다 한참 큰데 JVM 기본메모리가 잡혀있기 때문에 초과되어도 이정도는 정답이라고 한다.
그래서 카운팅정렬로 다시 풀었다. 입력받은 수를 인덱스로 하게 되면 최대 크기가 10,001까지 이므로 약 4MB가 된다. 시간초는 3초로 약 3x 1e8이니까 충분하다.