정렬

문제

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

내풀이

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

public class B2587 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		int[] arr = new int[5];
		int result=0;
		for (int i = 0; i < 5; i++) {
			arr[i] = Integer.parseInt(br.readLine());
			result +=arr[i];
		}
		System.out.println(result/5);
		
		Arrays.sort(arr);
		System.out.println(arr[(arr.length/2)]);
	
	}
}

문제

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

내풀이

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

import java.util.Collections;
import java.util.List;

public class B2751 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		List<Integer> arr = new ArrayList<>(); 
		
		for (int i = 0; i < n; i++) {
			arr.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(arr);
		for (int i : arr) {
			sb.append(i).append('\n');
			
		}
		System.out.println(sb);
	}

}

시간복잡도 O(n^2)를 못쓰는 문제임

Arrays.sort()의 시간복잡도 : 최악 O(n^2)
선택정렬의 시간복잡도 :O(n^2)
삽입정렬의 시간복잡도 : O(n^2)
버블정렬의 시간복잡도 : O(n^2)
퀵정렬의 시간복잡도 : 보통(O(nlogn),최악(O(n^2)
Collection.sorts()의 시간복잡도 :O(nlogn)

출력방법으로는 Stringbuilder를 사용하는게 좋음