[Java] 백준(브론즈-2) 2750번 - 수 정렬하기

입출력 예시

Input

5
5
2
3
4
1

Output

1
2
3
4
5

문제 풀이

---

이 문제는 N의 범위가 최대 1,000으로 작기 때문에 버블정렬을 활용해서 풀었다.

버블정렬 풀이

버블정렬이란?
데이터의 인접요소끼리 비교하고 swqp 연산을 수행하여 정렬하는 방식이다.

주어진 배열이 [5,2,3,4,1]일때, 버블정렬을 통해 정렬되는 과정을 알아보자.

i가 0일 때
    5>2 -> swap = [2,5,3,4,1]
    5>3 -> swap = [2,3,5,4,1]
    5>4 -> swap = [2,3,4,5,1]
    5>1 => swap = [2,3,4,1,5]
i가 1일 때
    2<3 = [2,3,4,1,5]
    3<4 = [2,3,4,1,5]
    4>1 -> swap = [2,3,1,4,5]
i가 2일 때
    2<3 = [2,3,1,4,5]
    3>1 -> swap = [2,1,3,4,5]
i가 3일 때 
    2>1 -> swap = [1,2,3,4,5]

위와 같이 i는 N만큼 순회하며 이전 수가 현재수보다 크다면 swap 연산을 수행한다.
여기서 핵심은 이중 for문은 n-i-1 만큼 반복한다는 것인데, 하나의 loop를 돈 후에는 끝자리 수들은 정렬이 완료되어 굳이 탐색할 필요가 없기 때문이다.

그럼 코드로 작성해보자.

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 tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;  
        }
    }
}

i는 주어진 입력 수 배열만큼 순회하며 이중 for문을 통해 인접 수들을 비교해가며 swap 연산을 수행한다.

작성코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for(int i=0; i<arr.length; i++ ){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        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 tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;  
                }
            }
        }
        
        for(int n : arr) bw.write(n+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 문제에서 주어진 N의 개수의 범위가 작기 때문에 n제곱의 시간복잡도를 가진 버블정렬에 대해서 공부하고 문제를 풀어볼 수 있었다.