불만 정렬( BOJ 5012 )

문제 : https://www.acmicpc.net/problem/5012

5012번: 불만 정렬

 

문제 파악하기

제시된 N개의 숫자 중 a_i > a_j > a_k(i<j<k)를 만족하는 수열의 개수를 찾는 문제입니다. N의 최댓값이 100,000개이기 때문에 완전탐색 알고리즘으로는 제한시간 안에 값을 찾을 수 없습니다. 문제를 해결하기 위해서는 적절한 자료구조 및 알고리즘을 사용해야 합니다.

 

문제 해결하기

제시된 조건을 만족하는 숫자 3개를 찾기 위해서는 세그먼트 트리를 활용해야 합니다. 세그먼트 트리를 사용해서 자신보다 오른쪽에 먼저 들어온 작은 숫자의 개수를 파악해야하며, 각각의 작은 숫자가  자신보다 오른쪽에 몇 개의 작은 숫자를 가지고 있는지도 파악해야 합니다. 이는 자신보다 작은 숫자를 가지고 있는 숫자를 선택하면 자동으로 조건을 만족하는 숫자 3개를 만들 수 있게 되기 때문입니다. 따라서, 자신보다 오른쪽에 위치한 작은 숫자들이 가지고 있는 각각의 작은 숫자의 개수를 모두 더하면 현재 숫자로 만들 수 있는 3개의 숫자 개수가 됩니다. 아래 수열을 예시로 설명해보겠습니다.

4

3

3

3

2

2

1

 

위 수열에서 효율적으로 3개의 숫자를 고르기 위해서는 숫자를 정렬해서 작은 숫자 순서대로 배열에 다시 넣어야 합니다. 그래야 위치를 가지고 자신보다 작은 숫자가 오른쪽에 있는지 확인할 수 있기 때문입니다. 그렇다면 위의 배열은 맨 처음 1부터 다시 들어가게 됩니다.

1(0)

 

그리고 1의 오른쪽을 보면 어떤 숫자도 없습니다. 그럼 다음 숫자를 넣어봅니다. 다음 숫자는 2가 가장 작지만 문제가 있습니다. 2가 2개가 있습니다. 이럴 때에는 우리 알고리즘을 생각해보면 정답을 떠올릴 수 있습니다. 우리는 항상 오른쪽에 어떤 숫자가 들어갔는지 확인합니다. 그렇기에 똑같은 숫자가 더 작다는 오류를 발생시키지 않으려면 가장 왼쪽에 있는 숫자부터 넣으면 됩니다. 따라서, 숫자를 2를 넣으면 다음과 같이 배열이 채워지게 됩니다.

2(1)

1(0)

 

숫자 2의 입장에서 오른쪽을 보면 자신보다 작은 숫자가 1개 있습니다. 따라서, 작은 숫자가 1개 있다는 표시를 해두면 됩니다. 하지만 1을 선택해서는 조건을 만족하는 숫자 3개를 만들 수 없습니다. 그럼 우선은 다음 숫자를 넣어봅시다. 다음 숫자 역시 위의 과정을 따라서 다음과 같이 배열이 채워지게 됩니다.

2(1)

2(1)

1(0)

 

여기서 다음 숫자를 넣어봅시다. 다음 숫자는 가장 왼쪽에 위치한 숫자 3입니다. 3을 넣으면서 오른쪽에 보니 자신보다 작은 숫자가 3개 있습니다. 그렇기에 배열은 다음과 같이 채워집니다. 하지만 이전과 다른 점이 하나 있습니다. 바로, 3의 오른쪽에 위치한 숫자 중에서 자신보다 작은 숫자를 가지고 있는 숫자가 존재한다는 것입니다. 2개의 2는 자신보다 작은 숫자를 1개씩 가지고 있으며, 3은 2를 선택하면 자연스럽게 조건을 만족하는 숫자 3개를 만들 수 있습니다. 그리고 만들 수 있는 총 가짓수는 1+1 = 2개가 됩니다. 그럼 우리는 최종 결괏값에 2를 더하면 됩니다.

3(3)

2(1)

2(1)

1(0)

 

나머지 숫자는 위의 과정을 따라서 탐색을 진행하면 최종 결괏값을 얻을 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
#define NMAX 100010
#define PAIR pair<int, int>
#define lint long long int
using namespace std;
 
int N, t;
vector< PAIR > inp;
 
int sz, idx;
lint segTree[NMAX*4][2];
 
lint rCnt, ret;
 
void update(int idx, int k) {
    while(idx > 0) {
        segTree[idx][k] = segTree[idx*2][k] + segTree[idx*2+1][k];
        idx /= 2;
    }
}
 
lint search(int l, int r, int k) {
    lint val=0;
    
    while(l<=r) {
        if(l%2==1) val = val + segTree[l++][k];
        if(r%2==0) val = val + segTree[r--][k];
 
        l/=2; r/=2;
    }
 
    return val;
}
 
int main() {
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d", &t);
        inp.push_back({t, i});
    }
 
    sort(inp.begin(), inp.end());
 
    for(sz=1;sz<N;sz*=2);
    for(int i=0;i<N;i++) {
        idx = inp[i].second;
        rCnt = search(idx+sz, N+sz, 0);
 
        // segTree[idx][0]: idx번째 위치의 숫자가 사용되었는지 체크하는 세그먼트 트리
        segTree[idx+sz][0] = 1;
        update((idx+sz)/2, 0);
 
        // [idx, N] 범위에서 자신보다 작은 숫자의 개수의 합
        ret += search(idx+sz, N+sz, 1);
 
        // segTree[idx][1]: 현재 숫자보다 작은 숫자의 개수
        segTree[idx+sz][1] = rCnt;
        update((idx+sz)/2, 1);
    }
 
    printf("%lld", ret);
 
}

후기

세그먼트 트리를 사용하는 여러 활용법 중 하나입니다. 세그먼트 트리를 활용할 수 있는 방법은 무궁무진하다는 걸 느낄 수 있는 문제라고 생각합니다. 세그먼트 트리를 연습하는 사람들에게 꼭 추천하고 싶은 문제입니다.