[Java] 4단계. 수 정렬하기2 [2751번]

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

• 예제 입력1

5
5
4
3
2
1

• 예제 출력1

1
2
3
4
5

---

• 문제 접근
  • 입력
    • 입력될 숫자 N (1 ≤ N ≤ 1,000,000)
    • N개의 숫자 입력
  • 출력
    • 오름차순으로 정렬
• 문제 해결
  • N의 최댓값이 100만이기 때문에 시간 복잡도가 O(n^2)의 알고리즘으로 풀게 되면 1조의 연산으로 10,000초(1억의 연산 = 1초) 소요
  • 시간 복잡도가 O(NlogN)으로 풀 경우 100만 * 20 = 2,000만 ⇒ 0.2초로 시간 제한이 문제 되지 않음
  • Arrays.sort 또는 Collections.sort는 평균 시간의 복잡도가 O(NlogN)이므로 두 개의 정렬 중 선택

• 기존 풀이 [메모리 : 185496 KB / 시간 : 4844 ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = parseInt(br.readLine());
    int[] arr = new int[N];
    for(int i = 0; i < N; i++)
        arr[i] = parseInt(br.readLine());
    br.close();

    Arrays.stream(arr).sorted().forEach(System.out::println);
}

private static int parseInt(String str){
    return Integer.parseInt(str);
}

• StringBuilder 사용 [메모리 : 110124 KB / 시간 : 1308 ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int N = parseInt(br.readLine());
    int[] arr = new int[N];
    for(int i = 0; i < N; i++)
        arr[i] = parseInt(br.readLine());
    br.close();

    Arrays.sort(arr);
    for(int num : arr)
        sb.append(num).append("\n");
    System.out.println(sb);
}

private static int parseInt(String str){
    return Integer.parseInt(str);
}

---

stream을 사용하게 되면 오버헤드가 발생하는 데다가 System.out.println은 엄청나게 시간을 소요하기 때문에 StringBuilder로 출력하는 것을 습관화