[백준] B2 2750번 수 정렬하기 1 (Java)

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

해당 문제는 'Do it! 알고리즘 코딩테스트 자바 편'을 보면서 공부한 내용입니다.

👉 문제

이번 문제는 간단하게 sort() 함수를 이용해서 풀 수 있지만, 정렬을 직접 구현해서 풀어보았다.

N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있습니다. 즉, 버블 정렬을 이용해 해결할 수 있습니다.

버블 정렬은 두 인접한 데이터의 크기를 비교해 swap 연산을 수행하며 정렬하는 방식입니다. 문제에서는 오름차순으로 정렬하라고 했으니 앞에서부터 인접한 데이터를 비교해 둘 중 큰 것을 뒤에다 배치하면 가장 큰 값이 뒤에 정렬되고, 최종적으로 모든 데이터를 정렬할 수 있습니다.

👉 풀이

import java.util.Scanner;

public class P2750_수정렬하기_1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            System.out.println(arr[i]);
        }
    }
}

👉 성능