백준 2751번: 수 정렬하기2(JAVA)

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

2751번: 수 정렬하기 2

 

[풀이]

(1) 처음에는 단순히 Arrays.sort()를 사용해 정렬을 하려고 했다. 그러나 Arrays.sort()는 퀵소트.. 평균 nlogn의 시간복잡도를 가지지만 최악의 경우 n^2 가 된다. N의 크기가 최대 1000000(백만)이므로 당연히 시간초과.

(2) 그래서 이 문제에서 시간복잡도 n의 카운팅정렬을 사용했다.

 

[코드]

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

public class BJ_2751_수정렬하기2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());

		boolean[] temp = new boolean[2000001];
		
		for(int n = 0; n < N; n++) {
			int num = Integer.parseInt(br.readLine());
			temp[num + 1000000] = true;
		}
		
		for(int n = 0; n < 2000001; n++) {
			if(temp[n]) {
				sb.append(n - 1000000).append("\n");
			}
		}
		System.out.println(sb);
	}
}

 

(참고) 틀린코드#1 - 시간초과

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

public class BJ_2751_수정렬하기2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr);
		
		for(int n = 0; n < N; n++) {
			System.out.println(arr[n]);
		}
	}
}

 

(참고) 틀린코드#2 - 역시나 시간초과.

Stringbuilder을 써줘야 시간초과가 안난다.

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

public class BJ_2751_수정렬하기2 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		int N = Integer.parseInt(br.readLine());
		
		boolean[] temp = new boolean[2000001];
		
		for(int n = 0; n < N; n++) {
			int num = Integer.parseInt(br.readLine());
			temp[num + 1000000] = true;
		}
		
		for(int n = 0; n < 2000001; n++) {
			if(temp[n]) {
				System.out.println(n - 1000000);
			}
		}
	}
}