[1377] 버블 소트 (JAVA)

# 문제 설명

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

---

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

---

출력

정답을 출력한다.

 

# 정답 코드

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

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

        int N = Integer.parseInt(st.nextToken()); //배열의 크기
        valueIdx[] A = new valueIdx[N];

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            A[n] = new valueIdx(Integer.parseInt(st.nextToken()), n);
        }

        Arrays.sort(A);

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

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

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

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

        @Override
        public int compareTo(valueIdx o) {
            return this.value - o.value;
        }
    }
}

 

이 문제는 swap이 한 번도 일어나지 않은 루프를 출력하는 문제이다.

 

10 1 5 2 3 (0)

1 5 2 3 10 (1)

1 2 3 5 10 (2)

1 2 3 5 10 (3)

 

기존 배열에서 범위를 바꾸며 버블 정렬을 실행한 예시이다.

파란색은 swap한 값들이고 괄호 속 글자는 범위를 바꾼 횟수이다.

범위를 바꾸고 swap하지 않으면 그 값을 출력하면 되므로 위 예시에서는 3이 정답이 된다.

그러나 예시처럼 버블 정렬을 구현하여 찾으면 시간 초과가 되므로 다른 방법으로 풀어야 한다.

 

기존 배열에서의 인덱스와 정렬된 배열에서의 인덱스의 차이가 가장 큰 값을 찾는다.

data	1	2	3	5	10
정렬 전 idx	1	3	4	2	0
정렬 후 idx	0	1	2	3	4
뺀 값	1	2	2	-1	-4

 

앞에 나왔던 예시로 계산하면 위와 같다.

뺀 값 중에서 가장 큰 값을 2이다.

버블 정렬을 구현하여 찾을 때의 빨간색 글씨처럼, 범위를 바꾸고 swap하지 않은 반복문이 실행되는 것을 감안하여 +1을 해주면 정답은 3이 된다.

 

값과 인덱스를 저장하는 배열을 사용하기 위해 valueIdx 클래스를 만들었다..

compareTo를 value를 기준으로 비교하도록 만들었다.

 

N번만큼 반복하며 배열 A를 채워준다.

그 다음 A를 value를 기준으로 오름차순 정렬한다.

 

정렬 전 인덱스에서 정렬 후 인덱스를 뺀 값의 최대값(max)를 찾아준다.

찾은 max에 1을 더해 출력한다.