[java 백준] 실버 5/2751번 수 정렬하기 2

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

2751번: 수 정렬하기 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
 
    public static int n;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        n = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(Integer.parseInt(br.readLine()));
 
        }
        Collections.sort(arr);
        for (int i : arr) {
            sb.append(i).append('\n');
        }
        System.out.println(sb);
 
    }
 
}

 

처음에는 선택정렬, 삽입 정렬로 풀어봤는데 알고보니 다들 시간복잡도가 엄청컸다..

그래서 다른 분들의 글을 찾아보니 Collections.sort로 풀린다 해서  ArrayList->Collections.sort로 풀어봤다

 

StringBuilder와 StringBuffer의 차이점!

---

나는 보통 입력 받을 때 시간초과가 나는 문제의 경우 Scanner보단 StringBuffer를 썼는데

이 문제는 StringBuffer를 쓰니 시간초과가 났다. (아마 문제는 StringBuffer보단 StringBuffer와 Collections.sort를 같이 쓰면 시간초과가 나는듯하다.)

그래서 StringBuilder와  StringBuffer의 차이점을 알아봤다!

 

StringBuffer은 동기화를 지원하지만, StringBuilder는 동기화를 보장하지 않는다. 

멀티 스레드 환경이라면 값 동기화 보장을 위해 StringBuffer를 사용하고, 단일 스레드 환경이라면 StringBuilder를 사용하는 것이 좋다. 

간일 스레드에서 StringBuffer를 사용한다고 문제가 되는 것은 아니지만 동기화 처리로 인해 StringBuilder에 비해 성능이 좋지 않다.

 

정리하자면 연산이 많은 경우 StringBuilder> StringBuffer이다!

 

참고 사이트

 

https://12bme.tistory.com/42

[자바] String, StringBuilder, StringBuffer의 차이

 

2022/02/05 추가 ) 병합정렬로 풀어보기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static int n;
    public static long[] arr;
    public static long[] sorted;
 
    public static void mergeSort(int start, int end) {
        if (start < end) {
            int middle = (start + end) / 2;
            mergeSort(start, middle);
            mergeSort(middle + 1, end);
            merge(start, middle, end);
        }
    }
 
    public static void merge(int start, int middle, int end) {
 
        int i = start;
        int j = middle + 1;
        int k = start;
 
        while (i <= middle && j <= end) {
            if (arr[i] <= arr[j]) {
                sorted[k] = arr[i];
                i++;
            } else {
                sorted[k] = arr[j];
                j++;
            }
            k++;
        }
 
        if (i > middle) {
            for (int t = j; t <= end; t++) {
                sorted[k] = arr[t];
                k++;
            }
        } else {
            for (int t = i; t <= middle; t++) {
                sorted[k] = arr[t];
                k++;
            }
        }
 
        for (int t = start; t <= end; t++) {
            arr[t] = sorted[t];
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        arr = new long[n];
        sorted = new long[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
 
        mergeSort(0, n - 1);
 
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb.toString());
 
    }
 
}