백준 2750: 수 정렬하기(java/python)

문제

---

풀이

 

버블 정렬으로 풀이하거나, 내장 함수 (파이썬)list.sort() 또는 (자바)Arrays.sort()를 사용해 간단하게 해결할 수 있다.

 

1. python_버블 정렬(Bubble Sort)

 

버블 정렬은 인접한 두 데이터의 크기를 비교하는 정렬 방법이다. 이중 for문을 사용하므로 \(O(N^{2})\)의 시간복잡도를 가진다. 앞뒤의 원소를 비교해, 앞의 원소가 더 크다면 뒤의 원소와 자리를 바꾼다.

N=int(input())

arr=[0]*N

for i in range(N):
    arr[i]=int(input())


for i in range(N-1):
    for j in range(N-1-i):
        if arr[j]>arr[j+1]:
            temp=arr[j]
            arr[j]=arr[j+1]
            arr[j+1]=temp

print(*arr, sep='\n')

---

2. python_list.sort() 사용

 

list.sort() 함수의 시간 복잡도는 \(O(NlogN)\)이다. 

N=int(input())

arr=[0]*N

for i in range(N):
    arr[i]=int(input())

arr.sort()

print(*arr, sep='\n')

위쪽이 list.sort(), 아래쪽이 버블 정렬

list.sort()를 사용한 풀이가 더 빠른 것을 확인할 수 있다.

---

3. java_Arrays.sort()

 

버블 정렬 알고리즘은 언어와 상관없이 동일하므로 생략

파이썬의 list.sort()와 마찬가지로 \(O(NlogN)\)의 시간복잡도를 가진다.

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		
		int[] arr=new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}

		Arrays.sort(arr);
		
		StringBuilder sb=new StringBuilder();
		
		for(int i : arr) {
			sb.append(i).append("\n");
		}
		
		System.out.println(sb);
	}
}

자바는 코드가 길어진다