[백준 : 2751/JAVA] 수 정렬하기2

---

java에서 제공하는 Arrays.sort(퀵sort)방법을 풀면, 평균 O(nlogn) 최악의 경우 O(N^2)이기 때문에 Collections.sort를 사용해야함

Collections.sort는 합병 및 삽입정렬 알고리즘을 사용하는 Timsort이다. 시간복잡도가 O(n) ~ O(nlogn)를 보장한다.

 

여기서 중요한거는 반복문을 돌려 System.out.println을 사용하게 되면 시간초과가 난다!

StringBuilder나 BufferedWriter를 사용해야함.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main_수정렬하기2751 {

	public static void main(String[] args) {
			
		Scanner scan = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int N = scan.nextInt();
		ArrayList<Integer> array = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			array.add(scan.nextInt());
		}
		
		Collections.sort(array);
		
		for(int value : array) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
		scan.close();
	}

}

CountingSort (계수 정렬) 사용하는 방법

Countingsort : 데이터의 값이 몇번 나왔는지 세주는 것 !

 

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();
        
		/*
		  -1000000 ~ 1000000
		  기준점 0 = index 100000 으로 생각
		*/
		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;
		}
 
		for(int i = 0; i < arr.length; i++) {
			if(arr[i]) {
				sb.append((i - 1000000)).append('\n');
			}
		}
		System.out.print(sb);
	}
}