[C++ 백준 풀이][Platinum V] 1517번 : 버블 소트 (세그먼트 트리 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1517번 : '버블 소트' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제를 풀이하기 위해 세그먼트 트리의 응용 개념이 사용됩니다.

물론 이 문제는 반드시 세그먼트 트리로만 해결할 수 있는 것은 아니고, 병합 정렬(merge sort)을 활용해서도 풀이할 수 있습니다만 세그먼트 트리를 배웠기 때문에 이를 활용해서 풀이할 것입니다.

 

 

1517번 : 버블 소트

 

버블 소트를 이용해서 데이터들을 정렬했을 때, 값의 swap이 몇 번 발생하는지를 구하는 문제입니다.

문제 자체가 버블 소트에 대한 문제이기 때문에 버블 소트를 이용하면 될 것 같지만, bubble sort는 O(N^2) 시간 알고리즘이므로 당연히 시간 초과가 발생하게 됩니다.

따라서 버블 소트 문제이지만 다른 방법으로 간접적으로 풀이해야하는 재미있는 문제입니다.

 

문제를 풀이하기 위해 세그먼트 트리를 활용할 것인데, 그 원리에 대해 설명하겠습니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 1000000001
using namespace std;

vector<pair<int, int>> Data; // first : value, second : index
vector<int> Tree;

void updateTree(int Node, int Begin, int End, int Index) {
    if(Begin == End) {
        Tree[Node] = 1;
        return;
    }
    int Mid = (Begin+End)/2;
    if(Index <= Mid) updateTree(Node*2, Begin, Mid, Index);
    else updateTree(Node*2+1, Mid+1, End, Index);
    Tree[Node] = Tree[Node*2] + Tree[Node*2+1];
}

int cntLess(int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftCnt = cntLess(Node*2, Begin, Mid, Left, Right);
    int rightCnt = cntLess(Node*2+1, Mid+1, End, Left, Right);
    return leftCnt + rightCnt;
}

int main() {
    int N, Value;
    long long Ans = 0;
    scanf("%d", &N);
    Tree.resize(N*4+1);
    Data.push_back({-INF, 0});
    for(int i=1; i<=N; i++) {
        scanf("%d", &Value);
        Data.push_back({Value, i});
    }
    sort(Data.begin(), Data.end());
    for(int i=1; i<=N; i++) {
        Ans += (long long)cntLess(1, 1, N, Data[i].second+1, N);
        updateTree(1, 1, N, Data[i].second);
    }
    printf("%lld", Ans);
}

 

잘 생각해보면 버블 소트는 값을 하나씩 오른쪽 끝으로 보내면서 자신보다 작은 값이 있으면 swap이 발생하므로, 어떤 값의 오른쪽에 자신보다 작은 값이 몇 개가 있는지를 모두 count 해주면 됩니다.

우선 정렬을 진행해주고, (이 때 원래 index 값을 저장한 상태로 정렬을 해주어야 원래 위치를 기억할 수 있으므로, pair를 사용하여 벡터를 정의해줍니다.) 가장 작은 값부터 세그먼트 트리에 대입해줍니다.

 

한 개의 노드에 대해서는 1을 저장하도록 하고, 하위 두 노드의 값의 합을 누적시켜서 상위 노드에 저장해줍니다.

값들을 세그먼트 트리에 대입하면서, 해당 수의 Index + 1 ~ 마지막 Index(= N) 중에서 더 작은 값이 있으면 swap이 발생하게 되므로, 해당 수의 Index+1 ~ N 구간에서의 구간 합을 리턴해줍니다.

구간 합을 리턴만 해도 바로 swap의 수를 구할 수 있는 이유는, 지금 정렬 후에 작은 값부터 트리에 하나씩 대입하면서 값을 체크하고 있기 때문입니다.

카운트와 update를 한 턴씩 진행하면서 트리에 값을 하나씩 대입해가면, 마지막에 총 swap의 횟수를 계산할 수 있게 됩니다.

 

 

위의 풀이 코드를 제출하면 320ms의 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

세그먼트 트리의 구간 합과 수정 기능을 넓은 범위로 응용하여 풀이했던 문제였습니다.

저는 세그먼트 트리를 활용할 생각조차도 못했는데, 버블 소트 알고리즘에 구간 합 개념을 끌어오는 것이 인상깊었던 문제였습니다.