[백준 온라인저지]수 정렬하기 - 정렬

수 정렬하기

이번 포스팅 문제는 2750 문제입니다. 시간복잡도 O(n^2)로 풀이했습니다.

문제요약

입력받은 숫자를 오름차순으로 정렬하여 출력하는 문제입니다.

풀이전략

1. 버블정렬로 풀이

구현하기

package BackJoon.수정렬;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/2750
 * 시간복잡도 O(n^2)
 * @author troh
 *
 */
public class _2750_수정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] arr = new int[count];
        
        for(int i=0; i<count; i++) {
            arr[i] = sc.nextInt();
        }
        
        arr = sort(arr);
        for(int i=0; i<count; i++) {
            System.out.println(arr[i]);
        }
    }
    
    private static int[] sort(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr.length-i-1; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}
 

배운점

버블 정렬은 시간복잡도 O(n^2) 란걸 다시한번 새겼으며 다시한번 정리해보았습니다. 같은 시간복잡도를 가지는 삽입 정렬에 대해서도 정리해보았습니다.