[백준 1377] 버블 소트(G2)

문제 바로가기

 

간단한 정렬문제인데, 왜 G2 문제지? 라고 생각하며 접근했다가 틀린 문제이다.

 

 

문제 요구사항을 요약하자면, 

버블정렬 알고리즘은 2중 for문으로 돌아간다. 

아래 예시로 예를들어보면

N=5,

배열 A는 10, 1, 5, 2, 3 이렇게 배열이 있을 때를 

i가 1일 때, 

j가 1부터 N-i 번 반복하게 된다.

 

i = 1 일 때,

[j=1]  1, 10, 5, 2, 3

[j=2] 1, 5, 10, 2, 3 

[j=3] 1, 5, 2, 10, 3

[j=4] 1, 5, 2, 3, 10

 

i = 2 일 때,

[j=1] 1, 5, 2, 3, 10

[j=2] 1, 2, 5, 3, 10

[j=3] 1, 2, 3, 5, 10

 

i = 3 일 때,

[j=1] 1, 2, 3, 5, 10

[j=2] 1, 2, 3, 5, 10

 

i=2, j=3 일때, 이미 정렬이 완료된 상태이다.

 

따라서 i=3일 때, 반복문이 도는 동안 한번도 swap이 진행되지 않아서

i=3 을 출력한다.

 

여기까지 문제를 이해했고 이제 이걸  어떻게 구현할까 고민해야한다.

 

단순하게 C++ 코드로 알고리즘을 떡하니 줬는데, 설마 저거 그대로 푸는게 답이겠어?

라고 생각하지 않고, 나는 그대로 풀었다. 결과는 "시간 초과"가 나왔다..

 

그 뒤로 어떻게 풀면 좋을지 고민을 해봤는데 도저히 답안이 생각 나지 않아서, 다른 자료들을 찾아봤다.

 

다른 블로그들을 여러개 찾아보면서 풀이 방법이 똑같아 보이지만 내가 이해가 잘 되지 않아서 제대로 정리해보려고 한다.

 

문제 풀이의 방법은 다른 자료들을 찾아봐도 아래와 같이 답을 한다.

특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이므로,

정렬전과 정렬 후를 비교해서 왼쪽으로 가장 많이 이동한 값이다.

 

10, 1, 5, 2, 3 인 초기 배열 상태에서 

1, 2, 3, 5, 10 최종 정렬 배열 데이터를 비교한다. 

오른쪽으로 이동(-),왼쪽으로 이동(+)로 표현하겠다.

이때 10은 4번 오른쪽으로 이동했으니 +4로 표현하겠다.

 

10: -4

1: +1

5: -1

2: +2

3: +2

 

이므로 답은 2+1인 3이라는것이다.

 

맨처음 이 답안을 보고 무슨 말인지 도무지 이해가 되지 않았다.

 

그런데 곰곰히 생각해보니 아래와 같은 이유였다.

외부 for문인 i마다 내부 for문인 j가 N-i 만큼 반복해서 비교하고 swap한다.

왼쪽의 값이 오른쪽의 값보다 큰 경우에 왼쪽값이 오른쪽으로 이동한다.

하나의 값을 기준으로 볼 때 오른쪽으로 가는 경우는 외부 for문 내에서는 여러번 갈 수 있다.

그러나 왼쪽으로는 한번밖에 가지 못한다.

 

이게 무슨 말이냐면

 

10, 1, 5, 2, 3에서 10을 기준으로 관찰해보자.

 

{외부 for문

i = 1 일 때,

 

    {내부 for문

        [j=1]  1, 10, 5, 2, 3

        1(+1), 10(-1)

 

        [j=2] 1, 5, 10, 2, 3 

        1(+1), 5(+1), 10(-2)

 

        [j=3] 1, 5, 2, 10, 3

        1(+1), 2(+1), 5(+1), 10(-3)

 

        [j=4] 1, 5, 2, 3, 10

        1(+1), 2(+1), 3(+1), 5(+1), 10(-4)

    }

}

 

이렇게 10은 오른쪽으로 4번 이동하고, 다른 작은 값들은 왼쪽으로 최대 한번 이동했다.

왼쪽으로 이동한 값이 즉 i의 반복 횟수를 넘을 수 없으며 똑같다는 것이다.

특히 swap을 했는지 안했는지 여부를 판별할 수 있다는 아이디어였다.

 

이걸 이해하는데 오래 걸렸다.. ㅠㅠ

 

그럼 이걸 어떻게 구현할까?

 

먼저 맨처음 풀이였던 버블 정렬을 이용해서 풀면 시간 초과가 났던 이유를 분석해보면

버블정렬은 N^2이기 때문이었다.

 

자바의 Arrays.sort()를 사용하면 nlogn이므로 시간문제는 없었다.

 

정렬전 수의 인덱스를 저장하고, 정렬 후의 인덱스와 비교한뒤

그 차를 구해서 풀면 된다.

 

 

 

class mData implements Comparable<mData> {
    int value;
    int index;

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

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

 

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        mData[] A = new mData[N];

        for (int i = 0; i < N; i++) {
            A[i] = new mData(Integer.parseInt(br.readLine()), i);
        }

        Arrays.sort(A);

        int Max = 0;

        for (int i = 0; i < N; i++) {
            if (Max < A[i].index - i) {
                Max = A[i].index -i;
            }
        }

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