• 백준 1377번 버블 소트:: 마이구미
    알고리즘 풀이/정렬 2016. 12. 28. 22:52
    반응형

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

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

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

    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

    반응형

    댓글 0

Designed by Tistory.