백준 3172 / C++

https://www.acmicpc.net/problem/3172

3172번: 현주와 윤주의 재미있는 단어 게임

 

[ 풀이 ] 

문자열을 우선 정렬해놓자. 이제 정렬후 인덱스로만 보면 처음 문자열의 사전순을 알 수 있다.

이 인덱스를 문자열과 함께 묶어서 들고다니자.

이제 정렬한 문자열을 모두 뒤집는다. 뒤집고 다시 정렬한다. 이제 순회를 시작해보자.

순회의 방향은 항상 뒤집은 문자열이 앞서는 순으로 진행된다. 그럼 좋아하지 않는 순서쌍이 되려면 

다음에 보는 문자열의 인덱스가  현재보는 문자열보다  커야한다. 

어떤 값보다 큰 원소의 개수를 세주고 값을 업데이트해주는건 펜윅트리로 O(logN)에 해주자. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string str[100001];
pair<string, int> a[100001];
ll n, tree[100001];

// fenwick tree 
void upd(int i, ll v) {
	while (i <= n) tree[i] += v, i += i & -i;
}

ll sum(int i) {
	ll ret = 0;
	while (i) ret += tree[i], i -= i & -i;
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> str[i];
	sort(str + 1, str + n + 1); // sort1
	for (int i = 1; i <= n; i++) {
		reverse(str[i].begin(), str[i].end());
		a[i] = { str[i], i }; // sort1의 인덱스 묶어서 저장 
	}
	sort(a + 1, a + n + 1); // sort2
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		// [idx+1, n] 에서 개수 카운팅 
		ans += sum(n) - sum(a[i].second);
		upd(a[i].second, 1);
	}
	cout << ans << '\n';
}