백준 1377번 버블 소트:: 마이구미

이번 글은 백준 알고리즘 사이트의 1377번 "버블 소트" 를 다뤄본다.

정답률은 20% 대로, 200명정도이다.

1377번 버블 소트 - https://www.acmicpc.net/problem/1377

이미 문제에서도 버블 소트의 소스를 보여줬다.

출력되는 정답이 의미하는 건 버블 정렬이 몇단계를 거쳤는지를 알아내는 것이다.

버블 정렬을 잠깐 살펴보자. (기본적으로 버블 정렬을 숙지하고 있다고 가정하겠다.)

다음과 같이 주졌다고 하자. (10 4 2 5 9 1)

10 4 2 5 9 1 -> 4 10 2 5 9 1 -> 4 2 10 5 9 1 -> 4 2 5 10 9 1 -> 4 2 5 9 10 1 -> 4 2 5 9 1 10

위의 경우가 1단계라고 하자.

그렇다면 다음이 2단계라고 할 수 있다.

4 2 5 9 1 10 -> 2 4 5 9 1 10 -> 2 4 5 9 1 10 -> 2 4 5 9 1 10 -> 2 4 5 1 9 10

이렇게 정렬이 될 때까지 단계가 늘어나게 된다.

계속 해보면 6단계까지 가게 된다.

다시 문제로 돌아가보자.

문제 그대로 소스로 제출한다면 시간 초과를 경험하게 된다.

이유는 알다시피 버블 정렬은 O(n^2)이다.

50000 *  50000 = 2500000000..........당연히 시간 초과다.

그렇다는 것은 다른 방법으로 접근을 해야한다.

이 문제의 접근은 버블 소트를 이용하는 것이 아닌 버블 소트 과정에서 보여지는 규칙을 이용하는 문제이다.

입력이 10 1 5 2 3 주어졌을 때 다시 단계별로 보자.

1단계               2단계

10 1 5 2 3     1 5 2 3 10

1 10 5 2 3     1 2 5 3 10

1 5 10 2 3     1 2 3 5 10

1 5 2 10 3     

1 5 2 3 10     

빨간색의 경우는 수가 크기 때문에 뒤로 가는 경우이고, 보다시피 swap을 할 때 뒤로 가는 것을 볼 수 있다.

빨간색이 아닌 것들의 경우는 앞으로 가는 경우이고, 보다시피 swap을 할 때 앞으로 이동한다.

뒤로 가는 경우는 생각하지말고 앞으로 가는 경우만을 생각하자.

현재 1단계에서는 1, 5, 2 가 앞으로 가는 경우이고, 2단계에서는 2, 3 이 앞으로 가는 경우다.

단계마다 앞으로 갈 경우 한칸씩 앞으로 가고 있다.

바로 이러한 규칙을 활용할 수 있다.

한칸씩 이동하기 때문에 특정 값이 몇칸 앞으로 이동했는 지를 구한다면 그것이 정답이 된다.

코드를 통해 표현하자면, 정렬 전과 정렬 후의 각 데이터들의 인덱스를 비교하는 것이다.

비교하여 인덱스 차이가 가장 큰 값 + 1 이 정답이 된다.

index와 value를 저장할 리스트를 만든 후 정렬 전과 후에 대해 각각 인덱스의 차이를 비교하는 소스를 구현하면 된다.

소스 구현도 어렵지 않기 때문에 버블 정렬의 규칙만 안다면 쉽게 풀 수 있다.

소스는 아래 Github URL을 통해 확인하기 바란다.

백준 1377번 버블 소트 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/sort/1377.java

백준 1377번 버블 소트

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

백준 1838번 버블 정렬

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