백준 1377 버블 소트 Java

정렬문제인 버블 소트이다.

제목 그대로 버블 소트에 관한 문제인데 버블 소트 코드가 주어지고

버블 소트가 더 이상 정렬할게 없을 때 i가 몇인지 즉 몇단계 인지를 출력해서 맞히는 문제이다.

 

주어진 코드를 그래도 사용해도 답은 다 맞는다. 다만 시간초과로 정답처리가 안된다.

버블 소트는 O(n^2)이기에 N이 500,000이면 250000000000번 연산하게 돼서 당연히 시간초과이다.

그래서 정답률이 30퍼센트 대 이다..

 

예제로 주어진 배열 10 1 5 2 3을 보면

i가 증가 될때 마다

10 1 5 2 3

1 5 2 3/ 10

1 2 3 /5 10  - > break;

이렇게 배열이 변하게 된다.

 

버블 소트는 뒤로 큰수를 뒤로 보내면서 정렬하는 방식이기에

뒤로 보내는걸 보지 않고 앞으로 이동되는 수가 원래 인덱스에서

몇 칸 이동했는지를 보면 해결할 수 있다.

1은 1칸, 2도 1칸, 3은 2칸이다.

제일 많이 이동한 칸수에 +1을 해주면 정답을 맞힐 수 있다.

내가 생각해낸 방법은 아니다...

 

하나의 배열을 만들어서 입력을 받은 수를 저장하고 저장된 수랑 같이 현재 인덱스를 저장해준다.

그 후 배열을 정렬시키고 원래 인덱스와 현재 인덱스의 차이를 Max값 찾는 알고리즘으로 구한다.

 

2차원 배열로 구현하면 Arrays.sort를 못쓰게되서 복잡해 지고 배열을 두개 만들면 원래 인덱스의

값을 구별할 수 없으므로 클래스를 하나 만들어서 Comparable 인터페이스를 구현했다.

 

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 reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        A [] arr= new A[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = new A();
            arr[i].value = Integer.parseInt(reader.readLine());
            arr[i].index = i;
        }
        Arrays.sort(arr);
        
        int max = 0;
        for(int i=0; i<n; i++) {
            if(max < arr[i].index - i)
                max = arr[i].index - i;
        }
        
        System.out.println(max+1);
    }
}
class A implements Comparable<A>{
    int value;
    int index;
 
    @Override
    public int compareTo(A o) {
        return this.value - o.value;
    }
}