[Java]백준_23968 : 알고리즘 수업 - 버블 정렬 1

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

 

 

 

 

문제 분석

버블 정렬로 k번째 교환되는 두 수를 구하는 문제이다.

먼저, 버블 정렬의 개념을 알아야 한다.

 

버블 정렬의 가장 기본적인 원리는 인접한 두 개의 수를 비교하여 큰 수를 오른쪽으로 밀어내며 정렬하는 알고리즘이다. 두 개의 수를 비교하여 만약 앞에 있는 숫자가 더 크다면, 서로 교환을 시키고 이후 다시 옆칸과 비교하는 방법을 반복한다.

배열 [5, 3, 8, 4, 2]로 동작 원리를 살펴보겠다.

 

<1회전>

• 5와 3 비교 -> 교환 -> [3, 5, 8, 4, 2]
• 5와 8 비교 -> 그대로 -> [3, 5, 8, 4, 2]
• 8과 4 비교 -> 교환 -> [3, 5, 4, 8, 2]
• 8과 2 비교 -> 교환 -> [3, 5, 4, 2, 8]

=> 가장 큰 값 8이 맨 뒤로!

 

<2회전>

• [3, 5, 4, 2, 8]에서 8은 이미 정렬 되었으니, 앞 네 개만 비교
• 3과 5 비교 -> 그대로 -> [3, 5, 4, 2, 8]
• 5와 4 비교 -> 교환 -> [3, 4, 5, 2, 8]
• 5와 2 비교 -> 교환 -> [3, 4, 2, 5, 8]

=> 앞 네 개 숫자 중 가장 큰 값이 뒤로 이동

 

...

 

이런식으로 버블 정렬 과정은 인접한 두 개의 값을 비교하여 계속해서 뒤로 보내는 알고리즘이다.

 

 

소스 코드 (⭕)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    cnt++;

                    if (k == cnt) {
                        System.out.println(arr[j] + " " + arr[j + 1]);
                        return;
                    }
                }
            }
        }

        if (cnt < k) {
            System.out.println(-1);
        }
    }
}

 

코드 분석

1. n과 k, 배열 값을 전부 입력받는다.

 

2. 버블 정렬은 한 번 돌 때마다 가장 큰 수가 오른쪽으로 이동한다. 바깥 반복문에 한 번 돌때마다 정렬이 완료된 구간이 하나씩 늘어나게 된다. 따라서, 바깥 반복문은 총 n-1번만 수행하면 된다.

 

3. 안쪽 반복문은 아직 정렬되지 않은 앞쪽 구간만 비교하면 되기 때문에 j < n - i - 1 조건으로 범위를 설정한다.

 

4. arr[j]와 arr[j + 1]을 비교하면서 큰 값을 뒤로 보내 swap을 진행한다. swap을 했다면 cnt로 카운트 해준다.

 

5. 만약, cnt가 k 값에 도달했다면 (=k번째 swap이 발생했다면) swap한 값 2개를 출력하고, cnt가 k보다 작으면 -1을 출력해준다.

 

 

 

end

정렬 개념은 알고 있었는데 실제 코드로 구현해 보는 것은 처음이다.

동작 원리는 쉬웠지만, 반복문의 조건 설정하는 것이 생각보다 어려웠다.