[BOJ] 백준 1377번 : 버블 소트 (JAVA)

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

1377번: 버블 소트

문제

영식이는 다음과 같은 버블 소트 프로그램을 C++로 작성했다.

bool change = false;
for (int i=1; i<=n+1; i++) {
    change = false;
    for (int j=1; j<=n-i; j++) {
        if (a[j] > a[j+1]) {
            change = true;
            swap(a[j], a[j+1]);
        }
    }
    if (change == false) {
        cout << i << '\n';
        break;
    }
}

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

풀이

버블 소트의 규칙성을 잘 파악해야하는 문제였습니다. 매 턴마다 각각의 요소에 대해서 swap을 여러 번하는 과정을 유심히 지켜봐야했습니다. 일단, 문제는 버블 소트지만, 저 코드를 그대로 쓰면 O(N^2)이기 때문에 100% 시간초과가 뜹니다. 처음에는 머지 소트로 접근해 볼까 했으나, 버블 소트와 메커니즘이 아예 다르므로 버블 소트의 규칙성에 집중하였습니다.

아래에서 증명을 하도록 하고, 풀이 자체만 설명드리겠습니다.

1. 숫자와 인덱스를 클래스 배열로 저장한다.

2. 숫자를 기준으로 배열을 오름차순 정렬한다.

3. 해당 숫자의 원래 인덱스와 정렬한 현재 인덱스의 차이를 구한다.

4. 인덱스 차이가 가장 큰 값이 정답이다.

 

증명

예제를 먼저 보겠습니다.

A = {10, 1, 5, 2, 3}이고 차례 차례 버블 소트를 진행해 보겠습니다.

 

(첫 번째 턴)

10 1 5 2 3

1 10 5 2 3

1 5 10 2 3

1 5 2 10 3

1 5 2 3 10

 

1은 앞으로 1칸(+1이라고 표기)움직였고,

2는 +1칸 움직였고,

3은 +1칸 움직였고,

5는 +1칸 움직였고,

10은 -4칸 움직였습니다.

 

(두 번째 턴)

1 5 2 3 10

1 2 5 3 10

1 2 3 5 10

 

1은 +0칸 움직였고,

2는 +1칸 움직였고,

3은 +1칸 움직였고,

5는 -2칸 움직였고,

10은 0칸 움직였습니다.

 

(3번째 턴)

1 2 3 5 10

 

이미 정렬된 상태이므로 더 이상 움직이지 않습니다.

따라서, 현재까지 움직인 현황은 보도록 하겠습니다.

1은 +1칸, 2는 +2칸, 3은 +2칸, 5는 -1칸, 10은 -4칸입니다.

 

그리고 문제에서는 더 이상 정렬이 발생하지 않는 인덱스를 구하라고 되어 있는데, 앞쪽 칸으로 가장 많이 이동한 숫자를 찾아야 합니다. 2와 3이 있는데 숫자 상 빠른 2를 선택하고, 이에 대한 실제 인덱스는 3이므로 3이 정답이 됩니다.

그렇다면, 왜 앞쪽 칸으로 많이 이동한 숫자의 인덱스가 정답이 될까요?

그 이유는 앞쪽 칸으로 가장 많이 이동해야하는 횟수가 5번이라고 가정하면, 이 숫자가 이동할 동안 나머지 1, 3, 4번과 같은 낮은 횟수를 가진 요소가 이미 이동이 끝나있기 때문입니다.

여기서 질문이 한 가지 더 나올 수 있습니다. "이동한 횟수 자체는 10이 더 많은데 왜 2를 고르는 것인가요?"와 같이 말이죠.

위에서 버블 소트를 실행한 과정을 보면 해답을 찾을 수 있습니다.

앞쪽으로 이동하는 요소는 1턴에 1칸이 최대인데, 뒤쪽으로 이동하는 요소는 1턴에 얼마든지 이동할 수 있습니다. 따라서, 같은 시간으로 기준으로 하였을 때, 앞쪽 칸만을 이동하는 숫자들만 비교해야하는 것입니다.

 

아래는 위 과정을 소스코드로 작성한 내용입니다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
class Point implements Comparable<Point> {
    int num; // 숫자
    int idx; // 인덱스
 
    Point(int num, int idx) {
        this.num = num;
        this.idx = idx;
    }
 
    @Override
    public int compareTo(Point o) {
        return num - o.num;
    }
 
}
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
 
        Point[] points = new Point[N + 1];
        for (int i = 1; i <= N; i++) {
            int temp = Integer.parseInt(br.readLine());
            points[i] = new Point(temp, i);
        }
        Arrays.sort(points, 1, N + 1); // 숫자를 기준으로 오름차순 정렬
 
        int max = 0;
        for (int i = 1; i <= N; i++) { // 해당 숫자의 인덱스가 몇 칸 움직였는지 계산
            max = Math.max(max, points[i].idx - i); // -> (이동한 횟수 - 1)번
        }
 
        bw.write((max + 1) + "\n"); // 위에서 구한 값은 (이동한 횟수 - 1)번이므로 1 더함.
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.