[코딩테스트] 백준 1377 자바

백준 1377

백준 1377 문제

위 문제에서 C++로 작성한 버블 소트 알고리즘은 바깥 루프가 몇 번째 반복을 할 때swap()이 일어나지 않는지 구하는 알고리즘이다. 버블 정렬에서 swap()이 일어나지 않았다는 것은 정렬이 완료됐다는 뜻이다.

그래서 해당 문제는 버블 정렬이 몇 번째 루프를 반복할 때 정렬이 완료된 걸 아는지 알아내는 문제이다.

하지만 해당 문제의 n의 최댓값은 500,000으로 O(n2)의 시간 복잡도를 갖는 버블 정렬을 사용하면 시간이 초과된다.

버블 정렬은 타겟 데이터가 왼쪽에서 오른쪽으로 swap()을 하며 정렬이 되는데, 그 외에 데이터들은 바깥 루프 한 번당 오른쪽에서 왼쪽으로 1칸씩 이동한다는 것이다.

따라서 시간 복잡도 O(n log n)의 Arrays.sort()로 정렬을 한 다음에 정렬 전 index - 정렬 후 index를 구하고 그것들 중에 최댓값 + 1를 하면 몇 번째 루프에서 정렬이 완료되는 것을 아는지 알 수 있다.

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

public class Boj1377 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 메모리 초과로 인해 BufferedReader 사용
        int n = Integer.parseInt(br.readLine()); // 데이터 개수
        Data[] data = new Data[n]; // 데이터 배열

        // 데이터 배열 저장
        for (int i = 0; i < n; i++) {
            data[i] = new Data(i, Integer.parseInt(br.readLine()));
        }

        Arrays.sort(data); // 데이터 배열 정렬, 시간 복잡도 = O(n log n)

        int max = 0; // 왼쪽 이동 최댓값 선언

        for (int i = 0; i < n; i++) {
            if (max < data[i].index - i) {
                max = data[i].index - i; // 데이터 배열의 [정렬 전 index - 정렬 후 index] 계산의 최댓값 저장
            }
        }

        System.out.println(max + 1); // 최댓값 + 1 출력

        br.close();
    }
}

class Data implements Comparable<Data> {

    int index;
    int value;

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

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

풀이

1. 정렬 전 index를 알아야 하고, value로 정렬을 하기 위해 Data라는 클래스를 Comparable 인터페이스를 구현하고, compareTo() 를 통해 value 기준으로 오름차순 정렬되도록 오버라이딩한다.
2. 시간 복잡도 O(n log n)을 갖는 Arrays.sort()를 통해 정렬한다.
3. 정렬이 완료될 때까지 가장 많이 오른쪽에서 왼쪽으로 이동한 횟수(=총 바깥 루프가 반복된 횟수)를 구하기 위해 정렬 전 index - 정렬 후 index를 해주며 가장 큰 값을 max에 저장한다.
4. 정렬이 완료 된 후에 다음 루프에서 정렬이 완료된 것을 알 수 있기 때문에 max + 1를 출력한다.