[BOJ] 백준 3006 터보소트

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

 Input 

3

2

1

3

 

 Output 

1

0

0

 

① 1의 교환횟수

arr  =  [5 4 3 7 1 2 6]

tree = [1 1 1 1 1 1 1] ← 단말 노드만 표시

    Bubble Sort와 같이 교환(swap)하기 때문에 결국, 『1』 앞에 몇개의 숫자가 존재하는지 필요합니다.

    세그먼트 트리에서 첫번째 부터 현재 숫자 『1』 앞 위치까지의 구간 합이 필요합니다. → [1, pos[1]-1] = [1, 4] = 4

    『1』은 이동하였기 때문에 『0』으로 표시하면 다음 구간합을 구할 때 제외처리 할 수 있습니다.

 

② 7의 교환횟수

arr  =  [5 4 3 7 1 2 6]

tree = [1 1 1 1 0 1 1] ← 단말 노드만 표시

     『7』을 뒤로 옮기는 것이기 때문에  『7』이 위치해 있는 곳 다음 지점부터 끝자리 몇개의 숫자가 존재하는 구해합니다.

    → [pos[7]+1, N] = pos[5, 7] = 2 

    → 『7』은 제일 뒤로 옮겨진 것이므로 기존 tree의 단말노드 위치에 『0』 표시

    ※ 옮기고자 하는 숫자가 애초에 제일 앞/뒤에 위치해 있다면 구간합을 구할 때

        [1, 1-1] = [1, 0] or [7+1, 7] = [8, 7]이 나올 수 있지만

        tree[0] = 0이며, tree 크기를 충분하게 잡기 때문에 overflow 되지 않습니다.

 

③ 2의 교환횟수

arr  =  [5 4 3 7 1 2 6]

tree = [1 1 1 0 0 1 1] ← 단말 노드만 표시

     『2』 앞에 몇 개의 숫자가 놓여있는 정보 필요 → 구간[1, pos[2] - 1] 합 =  [1, 5] = 3

▶ 이러한 규칙으로 6 → 3 → 5 → 4 까지 총 1 ~ N번 수행하면 됩니다.

 

Q) 각 숫자의 위치는 어떻게 저장할까? → pos[target] 배열 = target의 위치 = 값

arr  = [5 4 3 7 1 2 6]인 경우 → pos = [5 6 3 2 1 7 4]

ex) 4의 위치는 pos[4] = 2

 

Q) 1..N까지 좌우 교차로 순번을 어떻게 처리할까?

교환하는 순서는 1 → N → 2 → N-1 → 3 → N-2 ...  ▶ 총 N번으로 Two Pointer를 이용합니다.

앞으로 보내는 교환 순서 = 1 → 2 → 3 → ...  ▶ 총 (N + 1) / 2 = mid ▶ 1... mid

뒤로 보내는 교환 순서 = N → N-1 → N-2 → ...  ▶ N ~ mid+1

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int MAX_N = 1e5;
const int MAX_TREE_SIZE = 1 << 19;
int N, pos[MAX_N + 10];
// 구간 합 세그먼트 트리
int tree[MAX_TREE_SIZE];
 
void initTree(int n, int s, int e) { // n번 노드는 s~e구간 정보를 갖고 있음
    tree[n] = 0;
    if (s == e) return; // 단말 노드
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    initTree(L, s, m);
    initTree(R, m + 1, e);
}
 
int query(int idx, int start, int end, int queryLeft, int queryRight) {
    // 범위 벗어나는 경우
    if ((queryRight < start) || (end < queryLeft))
        return 0;
    // [s, e]가 Query범위 포함되는 경우
    if ((queryLeft <= start) && (end <= queryRight))
        return tree[idx];
    int mid = (start + end) / 2;
    int L = idx * 2;
    int R = L + 1;
    return query(L, start, mid, queryLeft, queryRight) + query(R, mid + 1, end,  queryLeft, queryRight);
}
 
void update(int n, int s, int e, int idx, int val) {//[idx] += val, val:-1 제거,  val:1 추가
    if (s == e) { // 단말 노드
        tree[n] = val;
        return;
    }
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    if (idx > m) update(R, m + 1, e, idx, val);
    else update(L, s, m, idx, val);
    tree[n] = tree[L] + tree[R];
}
 
void input() {
    scanf("%d", &N);
    int target;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &target);
        pos[target] = i; // target의 위치는 i
    }
    initTree(1, 1, N);
    for (int i = 1; i <= N; i++) {
        update(1, 1, N, pos[i], 1);
    }
}
 
void solve() {
    int left = 1, right = N;
    int mid = (left + right) / 2;
    int l = 1, r = N;
    int total = N;
    while (total--) {
        if (l <= mid) {
            printf("%d\n", query(1, 1, N, 1, pos[l] - 1));
            update(1, 1, N, pos[l], 0); // 기존 자리에서 제거
            l++;
        }
        if (r >= mid + 1) {
            printf("%d\n", query(1, 1, N, pos[r] + 1, N));
            update(1, 1, N, pos[r], 0); // 기존 자리에서 제거
            r--;
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    solve();
}