[백준] 2750 수 정렬하기 - 자바 JAVA

안녕하세요. 꼬맹입니다.

백준 2750번 수 정렬하기를 풀어봤습니다.

---

[백준 2750번 수 정렬하기 문제]

 

문제 링크 : https://www.acmicpc.net/problem/2750

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

 

N개의 수를 입력받아서 정렬해 출력하는 쉬운 문제였습니다.

---

[풀이]

 

우선 외우고 있는 정렬 기법이 버블정렬 밖에 없기 때문에 버블 정렬을 사용하고자 했습니다.

 

버블 정렬은

5 2 3 4 1 이라는 수 집합이 있을 때 앞에서부터 모든 수를 비교한다면 가장 큰 수는 맨 뒤에 위치한다는 정렬 기법입니다.

 

5 2를 비교하여 2 5 3 4 1 로 바꿉니다.

5 3을 비교하여 2 3 5 4 1 로 바꿉니다.

5 4를 비교하여 2 3 4 5 1 로 바꿉니다.

5 1을 비교하여 2 3 4 1 5 로 바꿉니다.

가장 큰 수였던 5가 맨 뒤에 위치하게 되었습니다. 이제 5는 볼 필요가 없습니다.

 

2 3을 비교하여 2 3 4 1 5 로 가만 둡니다.

3 4를 비교하여 2 3 4 1 5 로 가만 둡니다.

4 1을 비교하여 2 3 1 4 5 로 바꿉니다.

5 다음으로 큰 수였던 4가 5전에 위치하게 되었습니다. 이제 4 이후로 볼 필요가 없습니다.

 

2 3 을 비교하여 2 3 1 4 5 로 가만 둡니다.

3 1 을 비교하여 2 1 3 4 5 로 바꿉니다.

4 다음으로 큰 수였던 3이 4전에 위치하게 되었습니다. 이제 3 이후로 볼 필요가 없습니다.

 

2 1 을 비교하여 1 2 3 4 5 로 바꿉니다.

버블 정렬 끝 입니다.

 

버블 정렬의 시간 복잡도는 n개의 수가 있을 때 n-1 + n-2 + n-3 + ... + 1 번 연산하게 됩니다.

위 예시에서도 5개의 숫자가 있었고 4 + 3 + 2 + 1 번 연산해야 했습니다.

 

따라서 n(n-1)/2 번 연산하게 되고 O(N^2)의 시간복잡도를 갖습니다.

* 이미 정렬되어 있는 최고의 경우에는 O(N)의 시간복잡도를 갖습니다.

 

출처:  https://blog.encrypted.gg/922?category=773649

컴퓨터는 1초에 약 3-5억번의 연산을 한다고 합니다.

문제에서 주어진 수의 범위가 -1000부터 1000까지이기 때문에 버블 정렬 O(N^2)만큼인 4000000번 연산해도 1초에 3억번을 넘지 않습니다.

 

따라서 버블 정렬을 사용해도 괜찮습니다.

실제로 372ms로 문제를 통과했습니다.

 

그런데 지난 문제에서 정렬을 하기위해 Arrays 클래스의 sort 메소드를 사용했습니다.

이번엔 공부를 위해 직접 정렬 코드를 구현했지만 앞으로는 시간 절약을 위해 sort 메소드를 이용해야겠죠?

sort 메소드는 시간이 얼마나 걸릴까 궁금해 비교해봤더니 336ms로 문제를 통과했습니다.

 

아주 근소한 차이가 나지만 어쨋든 차이가 나는 이유가 궁금하여 Arrays 클래스의 sort 메소드는 어떤식으로 동작하는 건지 찾아봤더니 primitive type은 퀵소트를 객체 타입은 머지소트 혹은 팀소트를 이용한다고 하네요.

 

tim...sort..? 초면이어서 또 검색해봤습니다.

https://st-lab.tistory.com/276

자바 [JAVA] - 팀 정렬 (Tim Sort)

 

음~ 어렵네요! 안정정렬이며 합병절렬, 이중삽입정렬을 합쳐 최선이든 최악이든 더 최적화 되었다는 것 같아요.

 

 

다음 문제도 정렬문제인 거 같은데 팀소트는 초보 사냥터 왔는데 월드레이드보스를 만난 거 같은 느낌이라 우선 퀵소트를 이용해 봐야겠습니다.

---

[풀이 정리 및 코드]

 

단순한 문제였기 때문에 금방 풀이가 정리됐습니다.

 

1. 입력 받기

2. 버블정렬하기

3. 출력하기

import java.util.Scanner;

class Main{
    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();
        }
        //정렬하기
        int flag;
        for (int i = N; i > 0; i--){
            flag = 1;
            for (int j = 0; j < i - 1; j++){
                if (arr[j] > arr[j + 1]){
                    flag = 0;
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            if (flag == 1)
                break;
        }
        for (int i = 0; i < N; i++){
            System.out.println(arr[i]);
        }
    }
}