앞에 있는 수 중 자신보다 같거나 작은 수의 개수가 주어지므로, N번째 수는 N개의 수들 중 S_N 번째 값이다. 그 수를 제거하고, 마찬가지로 N-1번째 수를 결정한다. 이 방법으로 뒤 에서부터 수를 결정한다. i번째 수를 결정할 때는, 남은 (N-i+1)개의 수들 중에서 Si 번째에 있는 값을 찾으면 된다.(해법 1)
N개의 수들을 정렬한다. i번째 수를 결정할 때, 남은 수 중에서 Si 번째 수를 찾는다. i에 대해 Si 번째 수를 찾은 후 이 값을 리스트에서 제거한다. 리스트에서 값을 직접 제거하지 않고, 배열에 수를 사용했다는 표시를 해준다. 리스트에서 선형 탐색(linear search)을 통해 값을 찾는 데 O(N) 시간이 걸리므로, 총 시간복잡도는 O(N^2)이다.(해법 2)
기본적으로 위의 풀이와 방법이 같다. 마찬가지로 남은 수 중에서 Si 번째 수를 찾는데, 인덱스 트리 자료구조를 사용해서 탐색 시간을 O(N)에서 O(log N)으로 줄일 수 있다.먼저 N 개의 수들을 정렬한다. 인덱스 트리의 각 노드는 구간에서 제거되지 않은 수의 개수를 의미 한다. 즉, 초기에 단말노드 값은 1로 채워져 있다. Si 번째 수를 찾을 때, 처음에 인덱스 트리 의 루트에서 출발하여 왼쪽 노드가 �쿞i 개 이상이면 왼쪽 노드로, Si 개 미만이면 오른쪽 노드 로 이동한다.
이 과정을 단말노드까지 수행하면 O(log N)만에 Si 번째 수의 위치를 알 수 있다. 그 수를 제거할 때는, 단말노드에서 다시 루트까지 올라가면서 구간의 남은 수의 개수 를 1씩 줄인다.
예를 들어, 키가 10, 20, 30, 40으로 주어지고 S 배열이 0, 1, 1, 2로 주어졌다면, 10, 20, 30, 40 순서대로 단말노드의 값은 1, 1, 1, 1이다. 4번째 수는 30이 된다. 30을 제거하면서, 단말노드의 값은 1, 1, 0, 1로 된다. 이 때, 부모노드의 값도 갱신해준다. 전체 수가 3개 남았으므로 루트는 3, 아래 레벨의 노드의 값은 각각 2, 1이 된다. 3번째 수는 20 이 된다. 마찬가지로 20을 제거하면서, 단말노드의 값은 1, 0, 0, 1로 된다. 수가 2개 남았기 때문에 루트는 2가 된다. 2번째 수는 40이 된다. 인덱스 트리에서 두 번째 수를 탐색할 때, 루트에서 보면 왼쪽 자식 노드의 값은 1이므로, 왼쪽 구간에는 한 개의 수밖에 남아있지 않 다. 따라서 두 번째 수는 오른쪽 구간에 있다. 여기서 오른쪽 노드로 한번 더 이동하면, 결 국 40이 나온다. 첫번째 수는 마지막으로 남은 10이 된다. 따라서 순서는 10, 40, 20, 30이 된다.