[백준/Java] #1377 버블 소트

📝 문제 이름

사용 언어 : Java
레벨 : 골드 2

 

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

 

🔎 문제 설명

 

✅ 풀이

일단 처음에 문제를 정확히 이해를 못했었는데 여러 번 읽고 보니까 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 찾는 문제였다. 그래서 그냥 버블 정렬을 사용하면 되는거 아닌가? 라고 생각했으나 시간 제한 2초에 N의 최댓값은 500,000이기 때문에 시간초과로 풀 수 없고 다른 방법을 사용해야 했다.

 

안쪽 for 문이 실행되지 않는 순간 = swap이 발생하지 않았다 = 정렬이 완료됐다 라는 뜻이고, 나는 이 정렬 완료 시점을 찾아야 하는 것이다. 그러기 위해서는 정렬 전 인덱스와 정렬 후 인덱스가 필요한데 이 두 인덱스를 비교해서 각 데이터가 이동한 거리를 구한다 (정렬 전 인덱스 - 정렬 후 인덱스) 이 중에서 가장 멀리 이동한 데이터의 거리 (max) 값을 구하는데,

버블 소트는 정렬 여부를 확인하기 위해 한 번 더 반복문을 실행하므로 최종적으로 max + 1 값이 정답이 된다.

 

🤔 사실 max 값을 구해야 하는 것까지는 이해를 했었는데 max값에 +1을 하는 이유가 정확히 이해가 되질 않아서 chatGPT 에게 왜 +1을 해야하는지 물어봤다.

 

길게 답이 왔으나 요약하자면.

1. max : 모든 데이터 중에서 가장 많이 이동한 데이터가 정렬 완료에 가장 오래 걸린다.
2. 왜 max가 답이 되는가? : 데이터가 원래 위치에서 정렬된 위치로 가기 위해 최대 몇 번의 루프를 통과했는지 알아야 하기 때문이다.
3. 이제 스왑이 더 이상 발생하지 않는 첫 번째 루프는 바로 max 값만큼 루프를 돈 후, 추가로 한 번의 확인 루프에서 발생한다.

따라서 답은 max + 1 이 되는 것이다.

 

 

💻 최종 코드

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

public class Main {
    static class Num implements Comparable<Num>{
        int value;
        int idx;

        public Num(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }

        @Override
        public int compareTo(Num o) {
            return this.value - o.value;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        Num[] arr = new Num[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new Num(Integer.parseInt(br.readLine()), i);
        }
        // 정렬
        Arrays.sort(arr);
        int max = Integer.MIN_VALUE;

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

        bw.write(String.valueOf(max + 1));
        bw.close();
    }
}