[백준BOJ] 3006 터보소트

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

3006번: 터보소트

---

문제해설

정답률이 무려 70% 라서 여러풀이가 가능한 것 같습니다. 저는 "펜윅 트리"를 사용한 풀이를 해설 하도록 하겠습니다.

     for (int i = 1; i <= N; i++) {
          int data; cin >> data;
          update(i, 1);
          pos[data] = i;
     }

update는 위와같이 단지 자리를 1로 update 해주었고,

해당 data가 어느위치에 삽입되었는지 pos 배열에 저장 해주었습니다.

     for (int i = 1, j = N; i <= j; i++,j--) {
          int minPos = pos[i];
          int maxPos = pos[j];
          cout << query(minPos-1) << "\n";
          update(minPos, -1);
          if (i != j) {
               cout << query(N) - query(maxPos) << "\n";
               update(maxPos, -1);
          }
     }

제일작은값(1...)

제일 큰값(N...)

처리를 위해서 i++, j--를 이용함과 동시에 같다면 하나의 인덱스만 처리하고 반복문을 종료 하였습니다.

위의 코드는 해당 숫자보다 앞에 있는 숫자의 갯수를 출력하고

해당 숫자는 자기 자리를 찾아가게 되었으니 -1로 update처리 해주었습니다.

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

#define MAX_N 100000
int tree[MAX_N + 1];
int pos[MAX_N + 1];

void update(int target, int value) {
     while (target <= MAX_N) {
          tree[target] += value;
          target += (target & -target);
     }
}

int query(int target) {
     int ret = 0;
     while (target >= 1) {
          ret += tree[target];
          target -= (target &-target);
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N; cin >> N;

     for (int i = 1; i <= N; i++) {
          int data; cin >> data;
          update(i, 1);
          pos[data] = i;
     }

     for (int i = 1, j = N; i <= j; i++,j--) {
          int minPos = pos[i];
          int maxPos = pos[j];
          cout << query(minPos-1) << "\n";
          update(minPos, -1);
          if (i != j) {
               cout << query(N) - query(maxPos) << "\n";
               update(maxPos, -1);
          }
     }
}