[3006번] 터보소트

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 펜윅 트리 :: http://www.crocus.co.kr/search/펜윅 트리

이 문제는 그냥 부르트 포스하게 접근하면

총 n번 포문 O(n), 인덱스를 찾는데 O(n) 따라서 O(n^2)이라는 시간이 걸리게 된다.

이때 n제한이 10만이라 10만x10만 = 시간초과를 받게 된다.

따라서 이 문제를 다르게 생각해보자.

7
5 4 3 7 1 2 6

예제 입력 3을 기준으로 생각해보자.

모든 인덱스에는 1이라는 값이 들어가있다 생각하자

그럼 1 1 1 1 1 1 1이 될 것이다.

처음에는 1번 값을 찾아야 한다. 1번 값은 5번째에 있기에 앞으로 4칸을 당겨야 한다.

그러면 1 1 1 1 1 1 1에서 처음부터 5번째 인덱스까지 더해서 -1을 하면 4라는 값을 얻을 수 있다.

그 후 1 1 1 1 0 1 1으로 변경한다.

그다음 7을 옮겨야 하는데 4번째 인덱스에 있다.

이 값은 1 1 1 1 0 1 1에서 4번째 인덱스의 1부터 오른쪽으로 모든 합을 더하여 -1을 하게 되면 3 - 1 = 2라는 값을 얻을 수 있다.

그 후 1 1 1 0 0 1 1으로 변경한다.

이러한 방식으로 문제를 풀 수 있다면 이 문제는 펜윅트리로 접근이 가능해진다.

아래에는 펜윅트리로 문제를 해결한 코드를 수록해두었다.

pair로 두어 값, 인덱스를 고려하게 하고 펜윅트리의 update, sum을 이용하였다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> pii;
 
pii arr[100002];
int tree[100002];
int n;
 
void update(int i, int diff)
{
    while (i <= n)
    {
        tree[i] += diff;
        i += (i & -i);
    }
}
 
int sum(int i)
{
    int ans = 0;
 
    while (i > 0)
    {
        ans += tree[i];
        i -= (i & -i);
    }
 
    return ans;
}
 
int main()
{
    scanf("%d", &n);
 
    // 값과 인덱스를 pair로 받는다.
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i].first);
        arr[i].second = i;
 
        update(i, 1); // 각 인덱스에 1씩 값을 부여
    }
 
    // 값에 대해 정렬
    sort(arr, arr + n + 1);
 
    // p1은 처음부터 p2는 끝부터 시작
    int p1 = 1, p2 = n;
    for (int i = 1; i <= n; i++)
    {
        if (i % 2 == 1)
        {
            // p1의 인덱스에 해당하는 값을 sum, update
            printf("%d\n", sum(arr[p1].second) - 1);
            update(arr[p1].second, -1); 
            p1++;
        }
 
        else
        {
            printf("%d\n", sum(n) - sum(arr[p2].second - 1) - 1);
            update(arr[p2].second, -1);
            p2--;
        }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>