백준 1377 자바 - 버블 소트

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

1377번: 버블 소트

문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

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

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

코드

import java.awt.*;
import java.io.*;
import java.util.Arrays;

public class Main {
    private static int n;
    private static Element[] A;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        A = new Element[n + 1];
        for (int i = 1; i < n + 1; i++) {
            A[i] = new Element(Integer.parseInt(br.readLine()), i);
        }
        Arrays.sort(A, 1, n + 1);

        int max = 0;
        for (int i = 1; i < n + 1; i++) {
            max = Math.max(max, A[i].idx - i);
        }

        bw.write((max + 1) + "\n");
        bw.flush();
    }

    private static class Element implements Comparable<Element> {
        int num;
        int idx;

        public Element(int num, int idx) {
            this.num = num;
            this.idx = idx;
        }

        @Override
        public int compareTo(Element o) {
            return num - o.num;
        }
    }
}

풀이

문제의 코드를 그대로 쓰면 안되고 파악을 먼저 해야한다. 우리는 정렬이 더이상 되지 않을 떄의 인덱스를 출력해야 한다. 버블 소트에서는 한 번 정렬할 때(한 바퀴 돌 때) 숫자가 왼쪽으로는 한 칸만 움직일 수 있지만, 오른쪽으로는 무제한으로 움직일 수 있다. 왼쪽으로 움직이는 횟수를 파악해 가장 왼쪽으로 많이 움직인 인덱스를 찾으면 된다.