[Java] 백준 2750 수 정렬하기

rse·2023년 7월 11일
0

알고리즘

목록 보기
26/44
post-thumbnail

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

예제 입력

5
5
2
3
4
1

예제 출력

1
2
3
4
5

설명

위 문제는 버블정렬로 풀었다!

문제는 받은 숫자를 오름차순으로 다시 출력하면 되는 간단한 문제였다.

버블 정렬이란 오른쪽 숫자와 비교해서 크면 오른쪽과 자리를 바꾸고, 크지 않다면 가만히 두면서 끝에서 정렬을 완성하는 방식이다.

맨 처음 5 와 2를 비교한다. 5가 2보다 더 크므로 2와 5의 자리를 변경해준다.
다음으로 5와 3을 비교한다. 역시 5가 더 크므로 3과 5의 자리를 변경한다.
다음으로 5와 4를 비교한다. 5가 더 크므로 4와 자리를 변경한다.
다음으로 5와 1을 비교한다. 5가 더 크므로 1과 자리를 변경한다.

이렇게 해서 5는 정렬이 완료되었다.

두번째로 2와 3을 비교한다. 2는 3보다 작으므로 이동하지 않는다.
다음으로 3과 4를 비교한다. 3은 4보다 작으므로 이동하지 않는다.
다음으로 4와 1을 비교한다. 4는 1보다 크므로 이동한다.

이렇게 해서 4와 5가 정렬이 되었다.

버블정렬은 이렇게 오른쪽의 수와 비교해서 끝에서부터 정렬하는 방식이다.

시간복잡도는 O(n^2) 이 되겠다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] num = new int[n];

        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (num[j] > num[j+1]) {
                    int moment = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = moment;
                }
            }
        }
        for (int i = 0; i < num.length; i++) {
            System.out.println(num[i]);
        }
    }
}
profile
기록을 합시다

0개의 댓글