BOJ_1377 : 버블 소트

👉 문제링크

1377번: 버블 소트

---

---

🔸 문제 분석 🔸

• 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다.
• 버블 정렬의 이중 for문에서 안쪽 for문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 의미이고, 프로세스를 바로 종료해서 시간 복잡도를 줄일 수 있다.
  • 하지만 이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간 초과이다.
  • 안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어가 필요하다.
    • 안쪽 루프는 1에서 n-i까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap 수행
    • 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻
    • 데이터 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 문제를 해결할 수 있음 (정렬의 마지막 까지 이동한 인덱스가 가장 이동 횟수가 많음)

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        for (int i = 0; i < n; i++) arr[i] = new mData(Integer.parseInt(br.readLine()), i);

        Arrays.sort(arr);                   // arr배열 정렬 : O(nlogn)
        int max = 0;
        for (int i = 0; i < n; i++){
            if (max < arr[i].index - i)     // (정렬 전 index - 정렬 후 index) 계산의 최대값 저장
                max = arr[i].index - i;
        }
        System.out.println(max + 1);
    }
}
class mData implements Comparable<mData> {
    int value;
    int index;

    public mData(int value, int index) {
        super();
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(mData o) {     // value 기준 오름차순 정렬하기
        return this.value - o.value;
    }
}

🔸 코드 해석 🔸

• 자바에서 기본적으로 제공하는 sort() 함수로 배열을 정렬 : O(nlogn)
• 각 데이터 마다 정렬 전 index 값에서 정렬후 index 값을 빼고 최대값을 찾기
  • 그리고 swap이 일어나지 않은 반복문이 한 번 더 실행되는 것을 감안해 최대값에 1을 더해서 출력
• 정렬 전 index를 저장하기 위한 mData 클래스 정의
  • Comparable 인터페이스를 적용
    • compareTo() 메소드를 오버라이드해서 Arrays.sort()에서 value 기준으로 오름차순 정렬 할 수 있도록 함
      • 반환값이 음수이면 인수가 더 빠른 수
      • 반환값이 양수이면 클래스 멤버 변수가 더 빠른 수
    • mData 생성자에서 부모 클래스의 생성자도 호출해주어야 함

---

🔸 end 🔸

• 생각했던 것 보다 더 어려웠던 문제였다. 생각지도 못한 풀이법이 적용되서 교재 없이는 풀지 못했을 것 같다.
• 버블 정렬 예시 코드가 주어져서, 단순 버블 정렬 구현인가? 이게 왜 골드2지? 했는데 완전 잘못 생각했다.
  • 버블 정렬을 완전히 이해하고 있는지 물으며, 정렬 완료를 확인하는 방법으로 swap이 없는 루프 찾는 방법을 활용한 문제였다.
  • 그리고 더 나아가 정렬 완료가 몇 번째 루프인지 확인하기 위해, 인덱스 차이의 최대값이라는 새로운 접근방법이 필요했다.
• 이전에 버블정렬의 간단한 예시를 풀고와서, 문제에 주어진 c++코드의 버블정렬에서 바깥쪽 for문의 인덱스 범위가 N+1 까지인 걸보고 오타인가 생각했다.
  • 하지만 몇 번재 루프인지 출력하기 위해서 마지막 1회 더 반복을 위한 것이었고, 골드 2문제를 만만하게 본 내가 부끄러워졌다...
  • 이 부분에서 마지막 출력에 +1을 해야하는 작업도 추가시키는게 재미있었다.
• 버블 정렬의 활용을 보니 이해는 쏙 되면서도 어떻게 이런풀이가 있지 하면서 아주 흥미롭고 감회가 새로운 문제였다.