[java] 백준 1377번 문제(버블 소트)

원본 링크 : https://www.acmicpc.net/problem/1377

---

문제설명

 

소스코드

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

public class Boj_1377
{
    // 정렬 전 인덱스와 값을 저장하는 객체
    static class Pair implements Comparable<Pair>
    {
        int index; // index 저장
        int value; // value 저장

        // 생성자
        Pair(int index, int value)
        {
            this.index = index;
            this.value = value;
        }

        // 정렬할 때 이 메서드의 반환값에 따라 정렬 결과가 달라짐
        @Override
        public int compareTo(Pair o)
        {
            // 음수 반환: 현재 객체가 파라미터 객체보다 작다
            // 양수 반환: 현재 객체가 매개변수 객체보다 크다
            // 0 반환: 두 객체가 같다.
            return this.value - o.value;
        }
    }

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

        // n을 받아옴
        int n = Integer.parseInt(br.readLine());

        // 정렬 전 인덱스와 값을 저장하는 배열을 선언하고 초기화
        Pair[] arr = new Pair[n];
        for (int i = 0; i < n; ++i) arr[i] = new Pair(i, Integer.parseInt(br.readLine()));

        // Arrays.sort()는 내부적으로 정렬할 객체가 Comparable을 구현했는지 확인하고,
        // 구현했다면 해당 객체의 compareTo() 메서드를 사용하여 정렬
        Arrays.sort(arr);

        int max = 0;
        for(int i = 0; i < n; ++i)
        {
            int diff = arr[i].index - i; // 정렬 전 인덱스 - 정렬 후 인덱스
            if(diff > max) max = diff;
        }
        System.out.print(max + 1); // swap이 일어나지 않는 반복문이 한 번더 실행되는것을 감안하여 1 더해줌
    }
}

Pair 클래스는 Comparable 인터페이스를 구현한 구현 클래스이며, Comparable 인터페이스는 추상 메서드 compareTo()를 하나 가지고 있다.

compareTo() 메서드는 음수를 반환하면 현재 객체가 파라미터 객체(비교 대상)보다 작다는 것을 의미한다.

p1.compareTo(p2)​

Arrays.sort() 메서드는 내부적으로 정렬할 객체가 Comparable을 구현했는지 확인하고, 구현했다면 해당 객체의 compareTo() 메서드를 사용하여 정렬한다.

 

설명

• 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제
• swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬되었다는 것을 의미
• 이 문제는 N의 최대 범위가 500,000이므로 버블 소트로 풀면 시간 초과

 

핵심 아이디어

- 입력값의 원래 인덱스를 기억해 둔다.
- 값을 기준으로 정렬한 후, 정렬 전 위치(index) - 정렬 후 위치(index) 차이를 확인한다.
- 이 차이가 가장 많이 이동한 원소의 이동거리이며, 이는 버블 정렬에서 해당 값이 마지막으로 정렬되는 시점을 의미한다.

 

정렬을 수행하면 아래와 같은 그림으로 표현할 수 있으며 정렬 전 index 값에서 정렬 후 index 값을 빼고 최댓값을 찾는다.

swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 1을 더한다.

 

• 참고로 map을 사용하면 중복된 값이 있는 경우, 마지막 값만 저장되어 이전 값들이 덮어씌워져버린다.
• 그렇기 때문에 클래스를 사용해서 풀어야 한다.