[백준 1377] 버블 소트 (JAVA)

백준 1377번 문제  - 버블 소트

1377번: 버블 소트

---

문제 분석

 

• 정렬이 완벽하게 되어 더이상 스왑 동작이 일어나지 않았을 때, 버블 정렬한 횟 수

 

예시 ) 입력 : 다음 표 → 출력 : 3

 

버블 정렬 실행 횟 수	버블 정렬된 리스트 [10, 1, 5, 2, 3]
1	10, 1, 5, 2, 3 → 1, 5, 2, 3, 10
2	1, 5, 2, 3, 10 → 1, 2, 3, 5, 10
3	1, 2, 3, 5, 10 (더이상 정렬할 필요 없음)

 

---

해결 키 포인트

• 정렬이 되었을 때, 버블 정렬 횟수를 알아내는 방법 고안 
  • 문제에 첨부된대로 이중 for문을 사용 → 시간 초과 발생
  • 정렬된 리스트와 정렬 전 리스트 비교 ( 어떻게? )

• 버블 정렬이 1번 될 때, 일어나는 변화
  • 버블 정렬을 1번 할 때, 하나의 숫자가 리스트의 오른쪽으로 움직이는건 여러번 되지만 왼쪽으로 움직이는 건 1번만 가능
    ex) 10, 1, 5, 2, 3 → 1, 5, 2, 3, 10 
• 정렬된 리스트와 정렬 전 리스트를 비교하여 정렬 후 각 숫자들이 왼쪽으로 움직인 수의 최댓 값을 구한다
  → 이 값이 바로 정렬이 될 때까지의 버블 정렬 횟 수

 

비교를 통한 정렬 최대 횟수 구하기 예시

---

버블 정렬 설명

 

버블정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법으로 반복문을 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.

→ 시간복잡도: O(n^2) : 다른 정렬 알고리즘보다 속도가 느린편

Do It! 알고리즘 코딩 테스트 기본

---

코드

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());

        BubbleSort [] A = new BubbleSort[N];
        for(int i=0;i<N;i++){
            // index와 값을 함께 저장
            A[i] = new BubbleSort(Integer.parseInt(br.readLine()), i);
        }

        // 정렬
        Arrays.sort(A);

        // 정렬되기까지 버블 정렬 횟수
        int maxValue = 0;
        for(int i=0; i<N; i++) {
            int preIndex = A[i].index;
            if (preIndex - i > maxValue) {
                maxValue = preIndex - i;
            }
        }

        System.out.println(maxValue + 1);
    }
}

// 값과 인덱스를 모두 담을 수 있는 클래스 (sort할때 비교가 가능하게 Comparable 인터페이스 구현)
class BubbleSort implements Comparable<BubbleSort> {
    int value;
    int index;

    BubbleSort(int value, int index) {
        this.value = value;
        this.index = index;
    }

    // 비교를 해주는 함수 (value의 값이 크면 배열 끝으로)
    @Override
    public int compareTo(BubbleSort b) {
        return this.value - b.value;
    }
}