[백준] 2750번 수 정렬하기 - 버블 정렬 구현 / BubbleSort / 오름차순

문제

 

로직

배열의 크기 입력 받기

배열 선언 및 크기 설정

 

반복문

- 배열 값 입력 받기

 

while반복문

- 인덱스 변수 선언 및 초기화(i, j)

- 반복문

   - 앞의 배열 값이 뒤의 배열 값보다 클 때 -> swap

   - 인덱스 증가

- N값 감소 -> 반복 횟수 맞추기

 

*인덱스 변화

  i = 0, j = 1 -> i = 1, j =2 -> i = 2, j = 3 -> i = 3, j =4 

  N--;

  i = 0, j = 1 -> i = 1, j =2 -> i = 2, j = 3

  N--;

  i = 0, j = 1 -> i = 1, j =2 

  N--;

  i = 0, j = 1  

  N--; 

 

 

 

My Code

import java.io.*;


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] bubbleArray = new int[N];

        for(int i = 0; i<N; i++){
            bubbleArray[i] = Integer.parseInt(bf.readLine());
        }

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

 

 

 

문제의 핵심 & 알게된 점

굳이 버블 정렬이 아닌 다양한 방식으로 정렬 알고리즘을 구현할 수 있는 문제이다.

하지만 버블 정렬에 대해 이해하기 위해 구현에 버블 정렬을 이용했다.

이게 가능했던 것은 문제의 조건을 보면 시간 제한이 2초이고 정수의 범위가 1,000까지이기에

시간복잡도가 O(n^2)이어도 1,000,000가 되어 시간 제한에 맞게 구현할 수 있다.

버블 정렬의 시간복잡도는 O(n^2)이므로 가능했다.

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA