BOJ 5012 불만 정렬

< 출처 >
http://xoding.tistory.com/158
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220806808977

일단 구하고자 하는 세 수에서 가운데 수를 잡고, 가운데 수를 지정한 후 그 수보다 왼쪽에 있으면서 더 큰 수의 개수 오른쪽에 있으면서 더 큰 수의 개수를 곱해나가면서 답을 구할 수 있다고 한다.... 생각도 못했는데 대단하다...

그런데 여기서 어떻게 세그먼트 트리나 팬윅트리를 이용할 것이냐?

풀이와 코드를 봤지만 아직도 이해가 완벽히 되지 않았다.

일단 가운데 수를 앞에서부터 주어진 위치의 순서대로 보면서 나가보자.
가운데 수를 기준으로 왼쪽의 그 수보다 큰 수, 오른쪽의 그 수보다 작은 수가 각각 몇 개 있는지 알고 싶다. 세그먼트 트리나 팬윅트리에 무엇을 저장할 거냐면 처음에 입력받은 수의 개수를 저장할 것이다. 즉, 트리의 범위는 1에서 n까지가 되는 것이다.
그렇게 입력받은 수의 개수를 저장해두고 query(x, y)를 하면 주어진 수열에서 x이상 y이하의 수의 개수를 얻을 수 있는 것이다.

자, 왼쪽, 오른쪽을 각각 담당하는 트리 두 개를 만들자.  처음에는 일단 오른쪽 수들에 해당하는 트리를 입력받으면서 입력받은 수의 개수를 저장해 놓는다. 그리고 순서대로 볼 때, 왼쪽에 있는 자신보다 큰 수의 개수를 알고싶다. 맨 처음 수는 일단 왼쪽에 아무것도 없을 것이다. 그리고 실제로 왼쪽을 담당하는 트리에는 처음에는 아무것도 들어가있지 않다. 그럼 오른쪽을 보자. 오른쪽에 있는 수 중 자신보다 작은 수의 개수는 어떻게 구할까? 아까 만들어 놓은 오른쪽 담당 트리에서 현재 위치한 가운데 수보다 작은 수들의 합을 구하면 된다.
즉, query(1, cur-1)하면 될 것이다. 그러면 자신보다 오른쪽에 있으면서 작은 수들의 개수를 구할 수 있다.

그리고 다음이 중요하다. 이제 다음 가운데 수 후보를 볼텐데 넘어가기 전에 방금 가운데 수로 가정했던 수는 더 이상 다음 가운데 수보다 오른쪽에 있지 않기 때문에 오른쪽을 담당하는 트리에서 그 수에 해당하는 개수를 -1해서 지워버린다. 그리고 이제 다음 가운데 수 기준으로 왼쪽에 그 수가 들어가기 때문에 왼쪽을 담당하는 트리에서 그 수에 해당하는 개수를 +1해준다!

그렇다. 바로 트리 두 개로 왼쪽, 오른쪽에서 각각 어떤 수보다 크고 작은 수의 개수를 O(logN)만에 계산하되, 주어진 수들을 순서대로 보면서 더이상 어떤 수 기준으로 오른쪽에 있지 않은 수, 이제 왼쪽에 있게되는 수를 업데이트 해주면서 어떤 가운데 수를 기준으로 해서 원하는 값을 구할 수 있는 것이다.


그리고 트리를 하나만 사용하려면 왼쪽, 오른쪽의 개수를 따로 따로 구해서 배열에 넣어놓고 계산은 나중에 해주면 된다. 따로 구할 때 좋은 방법이 있는데, 트리에 값을 넣어놓지 말고 왼쪽의 경우 앞에서부터 보면서 집어넣고, 오른쪽의 경우 뒤에서부터 보면서 집어넣으면 된다. 아직 트리에 들어가지 않은 값들은 가운데 값보다 크다고 해도 왼쪽에 있는 값이 아니거나 작다고해도 오른쪽에 있는 값이 아니므로, 트리에 넣어주면서 즉 여태까지 살펴본 값들 중에서만 자신보다 작거나 큰 값의 개수를 세주면 된다!

그리고 이 문제는 +1, -1을 하기 때문에 Fenwick Tree가 편해보이는데, Segement Tree를 쓰더라도 조금 변형을 하면 된다. 여태까지 update(index, newValue...)에서 index에 해당하는 곳(leaf node)을 newValue로 교체했는데, index에 해당하는 leaf node에 +1, -1을 해주고 올라가면서 상위 노드들을 업데이트 해주면 되는 것이다. 간단한 것인데도 나는 블로그를 보고 알았다. 생각도 못했었다. 확실히 내가 아직도 세그먼트 트리에 대한 이해와, 응용력이 부족하다는 것을 느낀다.

< 출처 >
http://xoding.tistory.com/158
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220806808977