[백준] 3006 터보소트

터보소트는 1부터 N까지 총 N개의 수가 섞여있을 때만 사용할 수 있으며, 다음과 같이 N단계로 이루어져 있다.

• 첫 번째 단계에서 숫자 1의 위치를 찾는다. 그 다음 바로 앞의 숫자와 위치를 바꾸어가면서, 1이 제일 앞에 오게 바꾼다.
• 두 번째 단계에서는 숫자 N의 위치를 찾는다. 그 다음 바로 뒤의 숫자와 위치를 바꾸어가면서, N이 제일 마지막에 오게 바꾼다.
• 세 번째 단계는 숫자 2의 위치를 찾은 후에, 바로 앞의 숫자와 위치를 바꾸어가면서, 두 번째 위치에 오게 바꾼다.
• 네 번째 단계는 숫자 N-1의 위치를 찾은 다음에, 바로 뒤의 숫자와 위치를 바꾸면서, 뒤에서 2번째 위치에 오게 바꾼다.
• 다섯 번째 단계도 위와 같은 식으로 하면 되고 이를 N번 반복하는 것이다.

정리하면, 홀수번째 단계이면, 아직까지 고르지 않은 숫자 중 제일 작은 수를 고른 다음에, 그것을 인접한 숫자와 위치를 바꾸면서 올바른 위치로 이동시키고, 짝수번째 단계일때는, 제일 큰 수를 고른 다음에 위치를 이동시키는 것이다.

 

예제 입력 3

7
5
4
3
7
1
2
6

예제 출력 3

4
2
3
0
2
1
0

 

 

첫번째 단계(1) : 5번째로 나온 1. 왼쪽으로 이동해야 제자리를 찾기 때문에 왼쪽에 있는 수들의 개수의 합을 구해본다. = 4.

두번째 단계(7) : 4번째로 나온 7. 오른쪽으로 이동해야 제자리를 찾기 때문에 오른쪽에 있는 수들의 개수의 합을 구해본다. 이때, 오른쪽에 있는 수중에 이미 정렬되어 옆쪽으로 이동한 1이 있다. 따라서 개수의 합은 2가 된다.

세번째 단계(2) : 6번째로 나온 2. 왼쪽으로 이동해야 제자리를 찾기 때문에 왼쪽에 있는 수들의 개수의 합을 구해본다. 역시 이때도 왼쪽에 있는 수 중 이미 정렬돼, 이동한 수가 있으므로 그 수들은 제외해서 카운트한다. 따라서 개수의 합은 3이 된다.

네번째 단계(6) : 7번째로 나온 6. 오른쪽으로 이동해야 자리를 찾기 때문에 오른쪽에 있는 수들의 개수의 합을 구해본다. (7이 이동하여 6 옆에 있는 상태이지만, 7이 이동하면서 원래의 자리를 찾았기 때문에 6은 여기로 이동할 수 없다. 즉, 원래 입력받은 순서만 가지고 수를 카운트한다.) = 0.

.

.

.

1~N까지의 수들이 몇번째 입력으로 주어지는지 저장하고, 그 순서를 기준으로 왼쪽과 오른쪽에 몇 개의 수들이 있는지 누적합을 구하는 문제.

여기서 수들은 정렬을 통해 제거될 수 있음. (누적합의 값이 바뀜 → 세그먼트 트리)

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_N 100001

int N, n;
int pos[MAX_N];
int tree[MAX_N*4];

void update(int cur_node, int cur_left, int cur_right, int target_node, int value) {
    if (target_node < cur_left || cur_right < target_node) return ;
    
    tree[cur_node] += value;

    if (cur_left == cur_right) return ;
    update(cur_node*2, cur_left, (cur_left+cur_right)/2, target_node, value);
    update(cur_node*2+1, (cur_left+cur_right)/2+1, cur_right, target_node, value);
}

int query(int cur_node, int cur_left, int cur_right, int target_left, int target_right) {
    if (target_right < cur_left || cur_right < target_left) return 0;

    if (target_left <= cur_left && cur_right <= target_right) return tree[cur_node];

    return query(cur_node*2, cur_left, (cur_left+cur_right)/2, target_left, target_right) + query(cur_node*2+1, (cur_left+cur_right)/2+1, cur_right, target_left, target_right);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> n;
        pos[n] = i;
        update(1, 1, N, i, 1);
    }

    int left = 1, right = N, mid = (left+right)/2;
    
    for (int i = 0; i < N; ++i) {
        if (left <= mid) {
            cout << query(1, 1, N, 1, pos[left]-1) << '\n';
            update(1, 1, N, pos[left], -1);
            ++left;
        }

        if (right > mid) {
            cout << query(1, 1, N, pos[right]+1, N) << '\n';
            update(1, 1, N, pos[right], -1);
            --right;
        }
    }

    return 0;
}