백준 3006번: 터보소트 (플래티넘 IV)

 

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

3006번: 터보소트

 

터보소트라는 한번도 들어본 적 없는 정렬 알고리즘이 등장한다.

정렬하는 방식을 읽어보면 가장 원시적인 방식의 버블소트와 크게 다를 것이 없어보인다.

버블소트가 그냥 계속 앞으로 땡겨오는 것이라면 터보소트는 앞-뒤로 번갈아가며 보내주는 정도의 차이이다.

 

나무위키 피셜로는 실제로 "칵테일 소트"라는 버블소트의 하위 정렬 알고리즘이 있다고 하는데, 방식이 터보소트랑 완전 똑같다.

칵테일 섞는 것 마냥 정렬한다고 이름이 칵테일 소트라고 한다.

역시 개발자들의 작명 센스란;

 

터보소트(a.k.a 칵테일 소트)

 

아무튼 각 단계에서 숫자의 위치를 앞뒤로 바꾸는 횟수를 출력해주면 되는 문제이다.

현 순서인 숫자 앞 OR 뒤에 얼마나 많은 정렬되지 않은 요소가 있는지 세주면 되는 문제이므로 구간 합 세그먼트 트리를 이용해 풀어볼 수 있을 듯하다.

 

---

구간합 세그먼트 트리는 각 인덱스의 밀도를 파악하기 위해 쓰도록 하자.

즉, 세그먼트 트리로 1~8을 탐색하면, 1번~8번 구간의 숫자 개수를 뱉는다.

따라서 트리에는 0 또는 1만 들어간다.

 

앞과 뒤로 번갈아가며 숫자를 보내주어야 하므로, L과 R 변수를 각각 0과 N으로 초기화 한 후, 두 포인터 방식으로 탐색한다.

 

L번째로 작은 수 앞에 정렬되지 않은 요소가 몇 개 있는지가 곧 L번째로 작은 수를 옮기는 횟수이고,

R번째로 큰 수 뒤에 정렬되지 않은 요소가 몇 개 있는지가 곧 R번째로 큰 수를 옮기는 횟수이다.

 

L은 가장 작은 수, R은 가장 큰 수를 가리킨다. L이 가리키는 수보다 앞에 있는 수는 3개이므로, L은 앞으로 3번 옮겨야 한다. R이 가리키는 수보다 뒤에 있는 수는 2개이므로, R은 뒤로 2번 옮겨야 한다.

L과 R의 처리가 끝났다면, L과 R이 가리키는 수는 세그먼트 트리에서 빼주어, 뒷 계산에서 고려하지 않는다.

L이 가리키는 수보다 앞에 있는 "정렬되지 않은 수"는 7개이므로, L을 앞으로 7번 옮겨야 한다. R이 가리키는 수보다 뒤에 있는 "정렬되지 않은 수"ㄴ,ㄴ 4개이므로, R을 뒤로 4번 옮겨야 한다.

 

N이 짝수이면 L과 R이 같은 수가 되지 않고 끝나지만, 만약 N이 홀수라면 두 수가 같아진 후 while문이 끝나버린다.

이 때문에 중간에 있는 수가 몇번 옮겨지는지 출력되지 않는다.

(물론 이미 양쪽이 정렬된 후이므로 0이 출력된다. 예제 예시들이 0으로 끝나는 이유이다.)

 

따라서 L과 R이 같은 경우 하나만 처리해주는 로직을 추가한다.

 

// 터보소트
// 세그먼트 트리 & 두 포인터

#include <iostream>
#include <vector>

int N, a;
int pos[100001];
std::vector<int>segTree(1<<19);

int updateTree(int node, int s, int e, int ind, int val){
    if(ind < s || e < ind){
        return segTree[node];
    } else {
        if(s == e){
            return segTree[node] = val;
        } else {
            int mid = (s + e)/2;
            return segTree[node] = updateTree(node*2, s, mid, ind, val) + updateTree(node*2+1, mid + 1, e, ind, val);
        }
    }
}

int query(int node, int s, int e, int l, int r){
    if(r < s || e < l){
        return 0;
    } else {
        if(l <= s && e <= r){
            return segTree[node];
        } else {
            int mid = (s + e) / 2;
            return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
        }
    }
}

int main(){

    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> N;

    for(int i = 1; i <= N; i++){
        std::cin >> a;
        // 숫자 a의 위치 기록
        pos[a] = i;
        // 인덱스에 1을 넣어, 숫자 앞과 뒤의 다른 숫자들 개수를 셀 수 있도록 함
        updateTree(1, 1, N, i, 1);
    }

    int l = 1, r = N;

    while(l < r){
        std::cout << query(1, 1, N, 1, pos[l]-1) << '\n';
        updateTree(1, 1, N, pos[l], 0);
        l++;
        std::cout << query(1, 1, N, pos[r]+1, N) << '\n';
        updateTree(1, 1, N, pos[r], 0);
        r--;
    }

    if(l == r){
        std::cout << query(1, 1, N, 1, pos[l]-1) << '\n';
        updateTree(1, 1, N, pos[l], 0);
    }

    return 0;
}