[JAVA][백준][G2] 1377번 버블 소트

https://www.acmicpc.net/problem/1377

 

📒 문제

버블 소트 알고리즘을 다음과 같이 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]부터 사용한다.

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

 

● 시간 제한 / 메모리 제한

2 초 / 128 MB 

입력

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

 

출력

정답을 출력한다.

 

입출력 예

# 입력1
5
10
1
5
2
3

# 출력1
3

# 입력2
5
1
3
5
7
9

# 출력2
1

 

알고리즘 분류

• 정렬

---

💻 소스코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

         // 풀이 시작
        int N = Integer.parseInt(br.readLine()); // 배열의 크기

        myData[] arr = new myData[N];
        for(int i = 0 ; i < N; i++){
            int v = Integer.parseInt(br.readLine());
            arr[i] = new myData(i, v);
        }
        Arrays.sort(arr);

        int max = 0;
        for(int i = 0; i < N; i++){ 	// 정렬 전 index - 정렬 후 index 계산의 최댓값 저장
            if(max < arr[i].index - i)
                max = arr[i].index -i;
        }

        bw.write(max + 1 + "");

        bw.flush();
        bw.close();
    }
}

class myData implements Comparable<myData>{

    int index;
    int value;

    public myData(int i, int v){
        super();
        this.index = i;
        this.value = v;
    }

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

📝 풀이

해당 문제는 버블 정렬을 몇번 만에 완료 했는지 찾아내는 문제이다.

하지만 버블 정렬의 시간 복잡도는 O(n²)이므로 제한 시간 2초안에 통과할 수 없다.

 

버블 정렬은 왼쪽에서 오른쪽으로 swap을 수행하는데, 이는 특정 데이터가 한 루프 안에서 swap을 통해 왼쪽으로 이동할 수 있는 거리는 최대 1이라는 뜻이다.

즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 해당 문제를 해결 할 수 있다.