백준 #1849 순열(세그먼트 트리)

이번 문제는 N개의 배열에 1부터 N까지 한번씩만 숫자가 써져있는 a[i] 수열이 있을경우, A[i] 란 수열은 원래의 수열에서 i번째 수의 앞에 있는 수 중 i보다 큰 값이 있는 개수가 됩니다.

 

예를 들어서 원래의 수열이 2 7 3 5 4 1 8 6 이라고 한다면, 1 앞에 있는 숫자 중 1보다 큰 숫자는 5개가 있다,  2 앞에 있는 숫자는 없으므로 0이 됩니다.  그래서 만들어진 A[i] 수열은 5 0 1 2 1 2 0 0 이 됩니다. 

 

문제는 A[i] 수열로부터 원래의 수열을 찾는 것입니다.

 

i 값이 1인 경우는 간단하게 6번째 칸에 1이 존재한다는 것을 알 수 있습니다.

1

다음에는 2의 숫자의 위치입니다.  2의 숫자는 0이므로 가장 앞에 존재하겠죠.

2

1

다음은 3인데, 이 값은 1입니다.  이미 2가 앞에 있으니까, 그 숫자에서 한칸 건너띈 곳이 3이 있는 자리입니다.

2

3

1

4의 값인 경우에는 2 입니다.  비어있는 두 칸을 건너띄고 적어야 합니다.

2

3

4

1

5는 1의 값을 가지고 있으므로, 한칸을 건너띄고 적으면 됩니다.

2

3

5

4

1

6은 2의 값을 가지므로, 비어있는 두 칸을 건너띄웁니다.

2

3

5

4

1

6

7과 8을 모두 0이므로 첫번째 빈칸엔 7을 두번째 빈칸엔 8을 적습니다.

2

7

3

5

4

1

8

6

 

이렇게 빈 칸의 개수를 세면 됩니다.

 

그런데 이 빈칸의 개수를 일일이 센다면, 매 수행마다 $O(N)$의 효율이 되므로, 전체 알고리즘은 $O(N^2)$이 됩니다.

그래서 세그먼트 트리를 이용해서 저는 풀었습니다.

 

일단 모든 칸을 1로 채운 세그먼트 트리를 만듭니다.  처음에는 11111111 형태가 되겠죠.  그리고 합이 6이 되는 지점을 찾습니다.  왜 5가 아니냐면, i 숫자가 있는 칸보다 앞의 칸에서 i보다 큰 숫자를 세는 것이니까요.  달리 생각하면 i 숫자가 있는 칸에서부터 앞쪽으로 i보다 작거나 같은 수의 개수를 센다고 하면 이해하기 좋습니다.  그러면 왜 6을 찾아야 하는지 아니까요.   6번째칸까지의 합이 6이므로, 이 위치에 1을 쓰고, 세그먼트 트리에서는 해당칸을 0으로 만듭니다.  11111011 이 되겠죠.  2는 0의 값을 가지므로, 1의 합이 되는 지점을 찾습니다.  그러면 1이 나올테고, 그곳을 따로 기록하고 세그먼트 트리에서는 0으로 채웁니다.  01111011 형태가 될겁니다.  이를 반복하면, $O(N\log N)$의 알고리즘으로 풀 수 있습니다.

 

N의 범위가 100,000까지이므로, 세그먼트 트리 등을 사용해서 $O(N\log N)$이 아닌 알고리즘으로 풀면 시간초과가 발생합니다.

 

Segment Tree