[10989] 수 정렬하기 3

[백준 10989]
https://www.acmicpc.net/problem/10989

값을 입력받고 정렬시켜 출력하는 문제이다.

해당 문제에서 가장 중요한 점은 실행시간과 메모리를 최소화해야 한다는 점이다.

그렇기에 기존에 쓰던 방식과는 다르게 코드를 작성하여야 했다.

---

⭐️Scanner와 BufferedReader의 차이

Scanner는 입력을 받을 때 공백과 개행 문자를 자동으로 처리하기 때문에 추가적인 연산이 필요하다.

또한, 내부적으로 정규 표현식(Regex) 기반의 파싱 과정이 포함되어 있어 성능 저하 발생한다.

그러나 BufferedReader의 경우 한 줄 전체를 한 번에 읽고, 추가 가공 없이 그대로 반환하며
Scanner와 달리 정규식 기반 파싱이 없기 때문에 불필요한 연산이 줄어든다.

💡BufferedReader의 사용방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
...
public static void main(String[] args) throws IOException {
  BufferReader br = new BufferedReader(InputStreamReader(System.in));
  String temp1 = br.readLine();	// 문자열 입력
  int temp2 = Integer.parseInt(br.readLine());	// 정수형 입력
}

BufferedReader는 매개변수로 InputStreamReader를 사용하여 객체를 생성한다.

또한 메인 메서드에 throw IOException를 작성하여 의도치 않은 오류가 발생할 시 예외를 던져줘야 한다.

---

⭐️System.out.println과 BufferedWriter의 차이

두개 다 출력을 담당하는 기능을 가지고 있지만 작동하는 방식으로 인한 속도의 차이가 존재한다.

println()은 출력할 때마다 즉시 화면에 반영되므로 느린 속도를 가지고 있다.

그러나 BufferedWriter는 버퍼를 이용해 데이터를 임시 저장한 후, 한 번에 파일에 쓰기 때문에 특히 반복문에서 문장을 출력할 시에 대량의 데이터를 빠르게 출력할 수 있다.

💡BufferedWriter의 사용방법

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
String s = "abcdefg";   
bw.write(s+"\n");   //버퍼에 있는 값 전부 출력
bw.flush();  
bw.close();   

버퍼를 잡아놓았기 때문에 코드 마지막에 flush(), close()을 반드시 작성해주어야 한다.

---

🔧알고리즘 작성

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 cnt = Integer.parseInt(br.readLine());
        int[] list = new int[cnt]; 
        
        for (int i = 0; i < cnt; i++) {
            list[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(list); 
        
        for (int j = 0; j < cnt; j++) {
            bw.write(list[j] + "\n"); 
        }
        
        br.close();
        bw.flush(); 
        bw.close();
    }
}

우선 BufferedReader로 입력받은 정수들을 배열에 저장하였다.

이후 Arrays.sort() 메서드를 사용하여 배열을 정렬한 후 BufferedWriter를 사용하여 배열 안 요소들을 출력할 수 있었다.

BufferedReader와 BufferedWriter 같은 개념을 몰랐기 때문에 해당 개념을 학습 후에는 수월하게 문제를 해결할 수 있었다.

그러나 문제를 해결할 때 놓쳤던 부분이 존재했다.

---

⭐️정렬 알고리즘의 시간복잡도

최악을 기준으로 봤을 때 정렬 알고리즘은 O(NlogN) 부터 O(N^2)까지의 시간 복잡도를 가지고 있다.

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort (삽입정렬과 합병정렬을 결합한 정렬)	평균, 최악 : O(nlog(n))

해당 문제를 풀기 위해서 Collections.sort()와 Arrays.sort() 중 무엇을 사용할 지 고려해야 했으며, 최악의 경우를 고려했을 때 Arrays.sort()보다 Collections.sort()가 더 좋은 성능을 가졌음을 확인할 수 있었다.

해당 문제에서 실행 속도를 더 줄이기 위해서는 내가 사용한 Arrays.sort() 보단 Collections.sort()를 사용하는게 더욱 적합해 보인다.