[JAVA]1377 버블 소트, 정렬

 📚 문제  

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

 

 

🔍 아이디어  

버블 소트

• 버블 소트는 왼쪽에서 오른쪽으로 인접한 두 값을 비교하면서,
• 큰 값을 오른쪽으로 한 칸씩 밀어내는 방식으로 작동한다. (즉 작은값을 기준으로 오름차순 하고 있다)
• 한 패스를 돌 때마다 가장 큰 값이 끝으로 보내진다.

핵심 인사이트

• 버블 소트에서는 큰 값이 오른쪽으로 한 칸씩 이동하므로,
• 가장 많이 움직인 원소가 정렬 완료 시점을 결정한다. (왼쪽으로 이동한것들) 
• 이때 그 원소가 정렬된 위치에 도달하기까지 몇 번의 패스가 필요한지가 관건이다.

계산 방식

• 정렬 전 배열에서 각 값의 원래 인덱스 - 정렬된 인덱스를 계산한다.(정렬된 위치보다 원래 인덱스가 뒤에 있는 값, 앞으로 이동한 것들)
• 가장 큰 이동 거리에 +1을 해주면 정답이 된다. (마지막으로 움직인 그 값이 제자리 간 다음 패스에 swap이 더 이상 없어서 종료되기 때문.)

 

📝 풀이 

package 백준.정렬;

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

public class Boj_1377_버블소트 {
    static class Pair {
        int value, index;
        Pair(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Pair[] arr = new Pair[n];

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = new Pair(num, i); // 값 + 원래 인덱스 저장
        }

        Arrays.sort(arr, Comparator.comparingInt(a -> a.value)); // 값 기준 정렬

        int maxMove = 0;
        for (int i = 0; i < n; i++) {
            // 원래 인덱스 - 정렬된 인덱스
            int move = arr[i].index - i;
            maxMove = Math.max(maxMove, move);
        }

        System.out.println(maxMove + 1); // 패스 수 = 최대 이동 거리 + 1
    }
}