백준(2751번, 수 정렬하기 2, 실버V)

문제 내용

문제 내용

---

제출한 코드

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

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 numCount = Integer.parseInt(br.readLine()); 
        List<Integer> numbers = new ArrayList<>(numCount);

        for (int i = 0; i < numCount; i++) {
            numbers.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(numbers);

        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            sb.append(num).append("\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

---

후기

처음에는 이전에 풀었던 수 정렬하기 문제처럼 Arrays.sort()를 활용하면 해결할 수 있을 거라 생각했지만 제출 후 시간 초과가 발생했다.

Arrays.sort()에 대해서 찾아보니까 기본형의 배열들에 대해 Dual Pivot Quicksort를 수행해서
이 알고리즘의 평균 시간 복잡도는 O(n log n)이지만, 최악의 경우 O(n^2)의 시간 복잡도를 가지기때문에
Arrays.sort() 대신 Collections.sort()를 활용하고 StringBuilder를 사용하여 출력하는 방식으로 해결했다

Collections.sort(numbers);
	StringBuilder sb = new StringBuilder();
 	for (int num : numbers) {
 			sb.append(num).append("\n");
    	}

추가로 공부하면서 StringBuilder는 String과 달리 문자열을 추가할 때 새로운 객체를 생성하지 않고 기존 데이터에 덧붙이는 방식을 사용하므로, 연산 속도가 더 빠르고 메모리 부하도 줄어든다는 사실도 알게되었다

또한 이건 스터디로 팀원들과 얘기해보면서 알게된 내용인데, 정렬의 시간복잡도의 차이는 자바 버전에 따라 달라질 수도 있다고 하여 해당 부분도 감안해서 봐주면 좋을거같다...!

---

정렬 시간복잡도 개념

시간 복잡도 개념 참고