백준저지 10989번 수 정렬하기 3

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

10989번: 수 정렬하기 3

 

제출 날짜: 2021년 9월 1일 수요일

 

 

 

생각

문제의 메모리 제한이 8MB라고 적혀 있어서 더이상 못 풀고 있었는데 하단에 자바11은 512MB라고 적혀 있어서 다시 시도하게 되었다.

처음에는 그냥 입력을 쭉 받고 Arrays.sort()를 해서 통과했다. 그런데 다른 사람들 코드와 시간 차이가 많이 나서 확인해보니 대부분 카운팅 정렬을 쓰고 있었다. 입력 개수는 많지만 수는 10000 이하이기 때문에 가능한 방식이었다.

 

 

 

첫번째 코드 - Arrays.sort() 사용

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] numArr = new int[N];
        for (int i = 0; i < N; i++) {
            numArr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(numArr);
        for (int i = 0; i < N; i++) {
            bw.write(numArr[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

 

 

두번째 코드 - Counting Sort 사용

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] numArr = new int[10001];
        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(br.readLine());
            numArr[n]++;
        }
        for (int i = 1; i < 10001; i++) {
            for (int j = 0; j < numArr[i]; j++) {
                bw.write(i + "\n");
            }
        }
        bw.flush();
        bw.close();
    }
}