[백준 2751] 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

🤔 주의할 점

• 정렬
• 시간초과에 유의해 입출력과 정렬방식을 결정하자.

---

🎯 풀이

• Java의 Arrays.sort 로 풀면 시간초과 발생
• Timesort인 Collections.sort 와 buffer를 활용하는 StringBuilder의 사용으로 시간단축.

---

📌 코드

import java.util.Scanner;
import java.util.Arrays;

public class _2751 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int n = sc.nextInt();

        ArrayList<Integer> list = new ArrayList();

        for (int i = 0; i < n; i++) {
            list.add(sc.nextInt());
        }

        Collections.sort(list);

        for (int val : list) {
            sb.append(val).append('\n');
        }
        System.out.println(sb);
    }
}

---

🎯 풀이2

• 입출력에 BufferedReader와 BufferedWriter를 활용.

---

📌 코드2

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class _2751 {
    public static void main(String[] args) throws IOException { 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine()); 
        //BufferedReader는 String으로만 읽어옴. int로 변환필요.

        ArrayList<Integer> list = new ArrayList();

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

        Collections.sort(list);

        for (int val : list) {
            sb.append(val).append('\n');
        }
        System.out.println(sb);
    }

---

💡 알게된 것

• Arrays.sort()는 Dual-pivot Quicksort로 최악 시간 복잡도 O(n2)

• Collections.sort()는 합병 + 삽입정렬. O(n) ~ O(nlogn) 보장.

• StringBuilder는 append 와 insert를 통해 문자열을 저장. 버퍼를 활용하므로 메모리 관리 유리하며 속도 빠름.

• BufferedReader는 생성자 인자로 Reader 객체를 받는데, Reader는 추상클래스. 따라서 그 하위 클래스인 InputStreamReader를 인자로 받는다. BufferedReader는 입력 문자열을 버퍼에 저장해놓았다가 readLine() 메서드로 한줄을 한번에 읽는다.

  키보드 입력 -> InputStreamReader -> BufferedReader -> br.readLine();

• readLine 메서드는 IOException (입출력 예외)를 발생시킬 수 있다. throws IOException을 통해 예외 발생시 클래스 벗어나도록.

• List 는 ArrayList 상위의 인터페이스. List는 다른 종류의 list간 다형성 구현을 위해서만 사용.