[BaekJoon] 10989 수 정렬하기 (java)

🔗 문제 링크

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

👨🏻‍💻 내가 작성한 코드

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 Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		
		int[] arr = new int[num];
		for(int i=0; i< num; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr);
		
		StringBuilder sb = new StringBuilder();
		for (int i: arr) {
			sb.append(i+"\n");
		}
		System.out.println(sb.toString());
	}

}

👨🏻‍💻 다른 사람이 작성한 코드

import java.io.*;

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[] arr = new int[10001];
		
		for (int i = 1; i <= N; i++) {
			arr[Integer.parseInt(br.readLine())]++;
            		// 배열의 해당 위치값을 +1
		}
		
		for(int i = 1; i <= 10000; i++) {
			bw.write(String.valueOf(i + "\n").repeat(arr[i]));
            		// arr[]에 있는 수만큼 반복하며 해당 값을 출력
                    	// i가 0이면 무시하고 넘어가서 input에 있는 값들만 출력되게 된다.
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

📝 정리

문제를 풀고 효율이 높은 다른 사람의 코드를 보니 Sort에 소모되는 시간과 메모리를 아끼기 위해 조건에서 주어진 값의 수인 10,000의 크기의 배열을 생성하고 input값의 위치의 값을 +1씩 증가하는 방법으로 Sort에 소모되는 연산을 줄였다. (Counting Sort 알고리즘)

그 결과 아래의 사진과 같이 아래에 위치한 결과인 처음 내가 Sort를 하며 코딩한 결과보다 시간, 메모리사용 측면에서 모두 효율이 올라간 것을 확인할 수 있었다.

Counting Sort Algorithm

• 계수 정렬 알고리즘
• 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
• 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정한다.
• 데이터가 증장한 횟수를 센다.