백준 2751번 : 수 정렬하기2 (+System.out.println 반복사용의 단점)

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

2751번: 수 정렬하기 2

풀이

입력받은 값을 오름차순으로 정렬해주면 되는 간단한 문제다.

리스트를 정렬하기 위해서 Collections.sort메서드를 활용해서 

public class Main {
    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<T; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);
        for(int i: list) {
            System.out.println(i);
        }
    }
}

 

위와 같이 만들어 줬는데, 시간초과가 떴다..

 

근데 문득, 다른 블로그들에서 알고리즘 문제를 풀 때 StringBuilder로 문자들을 모아서 한번에 출력했던게 떠올랐다.

그래서 바로 사용해보니, 통과할 수 있었다.

public class Main {
	public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<T; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);
        for(int i: list) {
            sb.append(i+"\n");
        }
        System.out.println(sb);
    }
}

 

 

왜 이런 차이가 발생할까?

println함수를 살펴보면 아래와 같다.

public void println(Object x) {
    String s = String.valueOf(x);
    synchronized (this) {
        print(s);
        newLine();
    }
}

synchronized는 동기화라는 뜻으로

하나의 프로세스는 하나 이상의 스레드를 갖게 되는데, 같은 프로세스 안에 있는 스레드들은 데이터를 공유하게 된다.

이 때, 여러 스레드가 동시에 공유 데이터를 접근하게 하게 되면 데이터의 일관성이 지켜지지 않을 수 있는데,(여러 스레드가 동시에 데이터를 수정하는 경우) 이를 해결하기 위한 것이 바로 동기화이다.

 

동기화의 단점으로는 작업중인 스레드가 작업을 마칠 때 까지 다른 스레드들이 대기해야하는 '데드락(Deadlock)'이 발생하는 다는 것이다. 

즉, println함수는 synchronized가 적용되어  시간적 오버헤드(Overhead)가 발생하기 때문에 한 번 실행시 마다 시간적으로 손해를 보게 된다.

(이러한 이유로 프로젝트에서는 System.out.println으로 로그를 남기는 것을 지양해야한다.)

 

데드락(Deadlock) : 멀티스레드 또는 프로세스 간에 상호 배제적 자원에 대한 대기 상태가 서로 해결되지 못해, 시스템이 더 이상 진행하지 못하는 상태

시간적 오버헤드(Overhead) :  작업을 수행하는 데 소요되는 시간의 추가적 비용.
만약, A라는 작업이 10초이고 안전성을 위한 B라는 작업을 추가한 결과 12초가 걸리게 된다면 오버헤드는 2초가 된다. 

 

StringBuilder 대신 String 객체를 사용해서 모아찍을 경우

그렇다면 위와 같이 문자열을 StringBuilder의 append( ) 하는 것 대신 String의 concat( )을 사용해서 모아찍으면 안될까?

결과적으론 StringBuilder의 append( ) 처리 속도가 빠르다.

 

String객체는 문자열 마다 다른 주소를 갖게된다.

String str = "Hello";
str = str.concat("World");

만약 위와 같이 str에  concat을 써서 'World'를 추가한다면, str 기존주소가 HelloWorld라고 바뀌는게 아닌 새로운 주소에 HelloWorld라는 단어를 만들고 str은 새로운 주소를 참조하게 된다. 

값	주소
Hello	1000
HelloWorld	2000

즉, 객체 str의 값이 변하는 것이 아닌 문자열마다 주소를 만들어서 주소값만 바꿔서 참조하는 것이다.

그러나 StringBuilder의 경우

StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append("World");

sb객체에다가 단어들을 추가한다고 해서 문자열마다 새롭게 주소를 만들고 참조주소를 바꾸는게 아닌 딱 값만 바꾸게 된다.

 

이러한 과정으로 인해 StringBuilder를 통해서 한번에 모아 찍는것이 가장 빠르게 출력을 처리하는 것이 된다. 

---

참고문서

https://mygumi.tistory.com/83