백준 알고리즘 문제(79) - 수 정렬하기 2

Arrays.sort를 써서 풀었는데 시간초과가 걸리는 경우가 생겼다.

st-lab의 글을 참고하자면, Collections.sort()는 Timsort이기에 합병, 삽입 정렬 알고리즘을 사용한다. 합병 정렬은 nlogn의 시간복잡도를 가진다. 그리고 삽입정렬은 N^2 또는 최적의 경우 O(n)의 시간복잡도를 가진다.

그러므로, Collections.sort()를 사용하려면, ArrayList나 List 기능을 사용해야한다.

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

public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> list = new ArrayList<>(); //타입을 정해주지 않아도 된다.
		
		for(int i = 0; i< N; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		for(int value : list) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
	}
	
}

근본적으론 Arrays.sort와 같은 방법이지만 시간복잡도가 효율적일 확률이 높다.

그 다음은 countingsort를 이용한 방법이다. 범위의 중심을 기준으로 입력받은 값을 더해준 배열의 공간을 true로 바꿔주고, 모든 배열을 검증할때, true를 찾으면 그 배열에 해당하는 index - 범위의 중심(절반값)을 다시 빼준 값을 출력하는 것이다.

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


public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		StringBuilder sb = new StringBuilder();
		//절대값이1000000이하. 기준이 0이므로 index 1000000으로 시작
		//중복되는 수가 없으니 boolean 사용 가능.
		boolean[] arr = new boolean[2000001];
		int N = Integer.parseInt(br.readLine());
		
		for(int i =0; i<N; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000000] = true;
		}
		//기준점에서 입력한 수만큼 더한 배열이 true면 해당 공간index-1000000를 출력.
		for(int i =0; i< arr.length; i++) {
			if(arr[i]) {
				sb.append((i-1000000)).append('\n');
			}
		}
		System.out.print(sb);
	}
}

출처 : Stranger's Lab

물론 중복이 없으니 boolean을 쓸 수 있지만, 중복이 있는 경우에는 원래 과정이 추가되는 소요가 발생한다. 시간복잡도는 O(n)으로 매우 효율적이다. 가장 효율적인 방법이므로 countingsort를 활용해 숙달시켜야겠다.