BOJ1777 순열복원

 

1777번 순열복원

순열의 길이 N과 inversion sequence가 주어지면 이를 복원하여 원본 순열을 찾는다.

 

inversion sequence의 i번째 원소 = 원본 수열에서 i보다 뒤에 위치하고 i보다 작은 수의 개수

i보다 작은 수의 개수를 알고 있으니, 큰 수부터 원본 수열에서의 위치를 찾아주면 된다.

 

 

---

 

주어진 예시로 파악해보자 (inversion sequence = 반전 수열이라고 하자)

N=8, 반전 수열 = 0 1 0 2 2 1 2 0

 

1.

반전 수열의 여덟 번째 원소 0이 의미하는 바는

원본 수열에서 8보다 뒤에 위치하고 8보다 작은 수는 0개라는 뜻

따라서 원본 수열에서 8은 가장 마지막 위치에 있는, 여덟 번째 원소이다.

⇒ 원본 수열 = _ _ _ _ _ _ _ 8

 

2.

이제 반전 수열의 일곱 번째 원소 2를 보면

원본 수열에서 7보다 뒤에 위치하고 7보다 작은 수가 2개 있다는 뜻이다.

따라서 현재까지 복원된 원본 수열의 뒤에서부터 남는 칸을 세서 두 칸을 남길 수 있는 자리에 7을 넣으면 된다.

즉 7은 다섯 번째 원소

⇒ 원본 수열 = _ _ _ _ 7 _ _ 8

 

3.

반전 수열의 여섯 번째 원소 = 1

원본 수열의 뒤에서부터 한 칸을 남기는 자리는 6이므로, 6은 여섯 번째 원소이다.

⇒ 원본 수열 = _ _ _ _ 7 6 _ 8

 

 

---

 

따라서 이렇게 정리할 수 있다.

 

1 ≤ i ≤ N인 i의 원본 수열 상 위치는 다음을 만족하는 k이다.

• 1 ≤ k ≤ N
• 반전 수열의 i번째 원소 = 현재까지 찾은 원본 수열 상 k+1번째 칸부터 N번째 칸까지 비어있는 칸 개수

 

이때 k+1번째 칸부터 N번째 칸까지 비어있는 칸의 개수를 구하는 데에 팬윅트리를

두 번째 조건을 만족하는 k를 찾는 데에 이분탐색을 사용할 수 있다.

 

 

 

주어진 예시의 2번 상황의 경우 아래와 같이 k=5를 찾을 수 있다.

k=(1+8)/2=4일 때, 5번째 칸부터 8번째 칸까지 비어있는 칸의 개수 = 3

k=(5+8)/2=6일 때, 7번째 칸부터 8번째 칸까지 비어있는 칸의 개수 = 1

k=(5+6)/2=5일 때, 6번째 칸부터 8번째 칸까지 비어있는 칸의 개수 =2

⇒ 7을 원본 수열의 5번째에 배치하고 update(5) 실행

 

 

---

 

 

#include <iostream>
using namespace std;

int fen[1<<17]; //131072
int inversionSeq[100001];
int originalSeq[100001];
int N;

void updateFen(int idx) {
	while (idx <= N) {
		fen[idx]++;
		idx += (idx & -idx);
	}
}
int getSum(int idx1, int idx2) { //nonemptyPosCnt(idx1<idx<=idx2)
	int sum = 0;
	while (idx2) {
		sum += fen[idx2];
		idx2 -= (idx2 & -idx2);
	}
	while (idx1) {
		sum -= fen[idx1];
		idx1 -= (idx1 & -idx1);
	}
	return sum;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> inversionSeq[i];

	//initializeFen
	for (int i = 0; i < (1<<17); ++i) fen[i] = 0;

	for (int i = N; i; i--) {
		//find max k, 1<=k<=N s.t. N-k-(nonemptyPosCnt(k<i<=N))=inversionSeq[i]
		//then put i at position k, updateFen(k)

		int s = 1, e = N;
		int k = (s + e) >> 1;
		while (s < e) {
			int emptyPosCnt = N - k - getSum(k, N);

			if (emptyPosCnt > inversionSeq[i]) {
				s = k + 1;
			}
			else {
				e = k;
			}
			k = (s + e) >> 1;
		}

		originalSeq[k] = i;
		updateFen(k);
	}

	for (int i = 1; i <= N; ++i) cout << originalSeq[i] << " ";

	return 0;
}

 

 

 

어디선가 풀어본 건데 너무 오랜만이라 문제를 못 찾겠다 사실 시도조차 안 함

 

세그먼트 트리로 해도 되지만 팬윅트리가 더 편하다 세그먼트 트리는 좀 귀찮다...

 

잠이 안 와서,,, 진짜 오십 년 만에 백준 그리고 블로그 글

일이랑 관련 없는 것 좀 하고 싶었다.