[JAVA] 백준 2751번 【수 정렬하기 2】

---

 

정답을 맞추긴 했지만, 시간이 비정상적으로 높은 것 같아 다양한 방법을 시도했다.

 

1. BufferedReader 와 Arrays.sort()를 사용한 뒤, 향상된 for문을 사용해서 BufferedWriter로 출력하게끔 답을 제출했더니 1708ms 가 나왔다.

 

2. BufferedReader 와 Arrays.sort()를 사용한 뒤, 일반적인 for문을 사용해서 BufferedWriter로 출력하게끔 답을 제출했더니 1472ms 가 나왔다.

 

향상된 for문보다 그냥 for문 루프를 돌리는게 속도가 더 빠르다는 사실을 얼떨결에 알게 되었다.

 

3. BufferedReader 로 입력을 받은 뒤, Arrays.sort 를 사용하고 StringBuilder를 사용해서 데이터들을 저장한 뒤, 한번에 출력하게끔 구현하였더니, 1528ms 로 시간이 더 늘어났다.

 

 

---

 

 

 

속도가 늦어지는 원인으로 Arrays.sort 를 사용하는 과정에서 시간이 많이 소요됨을 알게 되었다.

 

그래서 Boolean 배열을 이용해서 정렬을 했다.

 

시간복잡도에서 차이가 나는 것 같은데, 시간복잡도 개념을 아직 잘 몰라서, 이 부분에 대해 공부를 해봐야겠다. ㅜㅜ

 

아무튼,

 

문제에서, 입력될 수 있는 수는 절댓값 1000000 이하의 정수라고 했으므로, 음수 값이 들어올 수 있음을 알 수 있다.

 

boolean 의 기본값은 false이기 때문에 , -1000000 ~ 1000000사이의 값이 입력되면 입력된 값에 해당하는 인덱스에 true 값을 입력하고, for문을 사용해서 해당 인덱스의 값이 true라면 인덱스 값을 출력하게끔 구현하면 된다.

 

따라서 인덱스 값은 음수 값이 될 수 없기 때문에, boolean 배열의 크기를 2000001 로 해야한다. 그리고 출력할 때, 1000000값을 빼주면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.valueOf(br.readLine()); //수는 절댓값이 1000000 보다 작거나 같은 정수가 주어진다.
		boolean [] array = new boolean[2000001]; //배열으 ㅣ크기는 2000001
		for(int i=1;i<=N;i++) {
			array[Integer.valueOf(br.readLine())+1000000]=true;
		}
        
        //입력되는 값의 인덱스를 true로 만듦.
        //만약 0이 입력되면 array[1000000] 값이 true가 될것이지만,
        //출력할 때, [인덱스-1000000] 값이 출력되도록 만들면 0이 출력 될 것
        
        
		for(int i=0;i<array.length;i++) {
			if(array[i]) {
				sb.append(i-1000000).append("\n"); //StringBuilder에 차곡차곡 쌓음
			}
		}
		System.out.println(sb); // 한번에 출력
		
		
	}
}