[백준 1377] 버블 소트 (Java) - 정렬의 시뮬레이션을 넘어서는 인사이트

🚀 문제의 함정

문제에 주어진 코드는 전형적인 버블 정렬(Bubble Sort)입니다. 하지만 데이터 개수 $N$이 최대 500,000이므로, 이를 그대로 $O(N^2)$으로 돌리면 반드시 시간 초과(TLE)가 발생합니다. 우리는 버블 정렬의 내부 동작 원리를 이용해 답을 유추해야 합니다.

💡 핵심 인사이트: 데이터의 이동 규칙

버블 정렬이 한 단계(for 루프 한 번) 진행될 때마다 데이터는 다음과 같이 움직입니다.
1. 오른쪽 이동: 한 번의 루프에서 큰 값은 오른쪽 끝까지 쭉 밀려날 수 있습니다.
2. 왼쪽 이동: 반면, 작은 값은 한 번의 루프에 단 한 칸만 왼쪽으로 이동할 수 있습니다.

따라서, 문제에서 요구하는 "버블 정렬이 몇 번째 단계에서 멈추는가"는 "정렬 전후를 비교했을 때, 왼쪽으로 가장 많이 이동한 거리가 얼마인가"와 같습니다.

🛠️ 해결 전략

1. 데이터와 인덱스 저장: 숫자 값(val)과 정렬 전의 위치(idx)를 하나의 객체(Node)로 묶어 관리합니다.
2. 정렬 실행: Java의 Arrays.sort()를 이용해 값을 기준으로 오름차순 정렬합니다 ($O(N \log N)$).
3. 거리 계산: (정렬 전 인덱스 - 정렬 후 인덱스)의 최댓값을 구합니다.
   • 결과값에 +1을 하는 이유는 문제의 for 루프가 정렬이 완료된 후 한 번 더 실행된 뒤 종료되기 때문입니다.

💻 구현 코드 (Java)

import java.io.*;
import java.util.*;

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

            // 값과 초기 인덱스를 함께 저장
            Node[] nodes = new Node[N];
            for (int i = 0; i < N; i++) {
                nodes[i] = new Node(i, Integer.parseInt(br.readLine()));
            }

            // 값을 기준으로 오름차순 정렬 (안정 정렬 유지)
            Arrays.sort(nodes, (e1, e2) -> Integer.compare(e1.val, e2.val));

            int maxDist = 0;
            for (int i = 0; i < N; i++) {
                // (정렬 전 인덱스 - 정렬 후 인덱스)의 최댓값 탐색
                // 왼쪽으로 이동한 거리가 가장 큰 값을 찾는다.
                maxDist = Math.max(maxDist, nodes[i].idx - i);
            }

            // 정렬이 완료된 직후 한 번 더 루프를 돌고 종료되므로 +1
            System.out.println(maxDist + 1);
        }
    }

    static class Node {
        int idx;
        int val;

        public Node(int idx, int val) {
            this.idx = idx;
            this.val = val;
        }
    }
}

🧐 기술적 고찰

• Stable Sort의 중요성: 값이 같은 데이터가 여러 개 있을 때, 상대적인 순서가 유지되어야 정확한 이동 거리를 계산할 수 있습니다. Arrays.sort()는 객체 배열에 대해 Stable Sort(TimSort)를 보장하므로 안전합니다.
• 역발상의 힘: 시뮬레이션 문제를 만났을 때 규칙성을 찾아내어 다른 알고리즘(정렬)으로 치환하는 과정이 알고리즘 문제 풀이의 핵심임을 다시금 느꼈습니다.