[COCI] 백준 3006 - 터보 소트

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

Intro

칵테일 정렬의 과정을 표현한 그래픽 출처 - 위키피디아 칵테일 정렬 문서

 

문제를 잘 읽어보면 칵테일 정렬과 비슷한 논리로 진행됨을 이해할 수 있다. 그렇다고 진짜 칵테일 정렬을 수행하면 $O(N^{2})$의 시간복잡도로 참사가 일어날 것이 분명하다. 그렇다면 우리는 이 문제를 어떻게 풀어야 할까?

아이디어

위 gif 이미지를 보면 배열의 양 끝이 정렬되는 것을 알 수 있다.

 

그리고 우리는 정렬된 부분을 다시 건드리지 않는 것이 최적임을 너무나도 잘 알고있다.

 

이를 바꿔서 생각하면 터보 소트의 동작이 수행될 때마다 나머지 원소들이 정렬을 위해 이동해야 할 최대 거리가 1씩 줄어든다는 것이다.

 

그렇다면 정렬이 진행되는 과정에서 각 원소가 이동해야 하는 거리를 효율적으로 계산하면 괜찮을 거라는 생각을 할 수 있다.

 

구간합을 저장하는 펜윅 트리를 통해 이를 구현해보자.

구현

다음 정보를 구간합으로 보관할 것이다.

 

각 원소에 해당하는 index가 터보 소트의 동작으로 정렬된 상태면 0, 그렇지 않으면 1

 

초기화는 당연히 리프 노드가 1이 되도록 한다.

 

트리를 초기화 하고 나면 원소가 정렬되기 위해 움직여야 하는 거리 $O(\log N)$ 구간합 질의로 빠르게 처리할 수 있다.

 

정렬되지 않은 원소들의 최소 -> 최대 -> 최소 -> 최대 -> ... 순서대로 정렬이 수행된다는 사실에 주의하며 스왑 횟수를 구하면 된다.

 

스왑 횟수를 구한 다음 해당 index에 1을 빼준다. 1을 빼주는 의미는 해당 인덱스의 원소는 정렬되어 끝으로 간 상태이므로 그만큼 스왑 횟수에 반영하지 않겠다는 뜻이다.

 

이렇게 구간합과 1을 빼주는 질의를 각 원소마다 출력해주면 AC를 받을 수 있다. 최소 -> 최대... 원소를 뽑아내는 부분은 아래 구현을 참조하면 된다.

 

전체 코드

#include <bits/stdc++.h>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
using ll = long long;

int n;
int idx[100001];
int fenwick[100001];

int sum(int pos)
{
    int ret = 0;

    while (pos)
    {
        ret += fenwick[pos];
        pos &= (pos - 1);
    }

    return ret;
}

void add(int pos, int val)
{
    while (pos <= n)
    {
        fenwick[pos] += val;
        pos += (pos & -pos);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        idx[x] = i;
        add(i, 1);
    }

    for (int i = 1; i <= (n + 1) / 2; ++i)
    {
        int l = i, r = n - i + 1;

        if (l != r)
        {
            cout << sum(idx[l]) - 1 << '\n';
            add(idx[l], -1);
            cout << sum(n) - sum(idx[r]) << '\n';
            add(idx[r], - 1);
        }
        else
        {
            cout << sum(idx[l]) - 1 << '\n';
        }
    }
}