[백준 5867] Scrambled Letters

문제

www.acmicpc.net/problem/5867

5867번: Scrambled Letters

 

풀이

문제 내용을 간단하게 해석하자면 N개의 문자열이 주어질 때, 각각의 문자열을 재 정렬하고 나서 각 문자열마다 가능한 최소 위치, 최대 위치의 인덱스를 출력하는 문제입니다.

---

1. "모든 문자열에 대해서 각각의 문자열을 오름차 순으로 정렬한 배열" = miv

   "모든 문자열에 대해서 각각의 문자열을 내림차 순으로 정렬한 배열" = mav

   "모든 문자열에 대해서 각각의 문자열을 오름차 순으로 정렬한 후, 배열을 오름차 순으로 정렬한 배열" = low

   "모든 문자열에 대해서 각각의 문자열을 내림차 순으로 정렬한 후, 배열을 오름차 순으로 정렬한 배열" = high

   라고 합시다.    

 

2. i번째 문자열이 들어갈 수 있는 최소 위치는 high에서 miv[i]가 들어갈 수 있는 위치와 같습니다. 이는 lower_bound의 정의와 같기에 쉽게 구할 수 있고, high배열이 0-Index이기에 +1해줍니다. 

 

3. 최대 위치는 low에서 mav[i]가 들어갈 수 있는 위치와 같습니다. 이는 최소 위치와 마찬가지로 upper_bound를 통해서 구할 수 있는데 low배열에 들어가 있는 (정렬한) i번째 문자열은 항상 upper_bound로 구한 위치의 왼쪽에 한 개가 이미 존재하여 중복이 됩니다. 따라서 왼쪽에 존재하는 1개를 빼고 0 -Index 처리를 위해 +1 해주면 최대 위치는 upper_bound로 구한 인덱스가 정답입니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
int n, p1, p2;
string s;
vector<string> low, high, miv, mav;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n;
	miv.resize(n), mav.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> s;
		sort(all(s));
		miv[i] = s;
		low.push_back(s);
		reverse(all(s));
		mav[i] = s;
		high.push_back(s);
	}
	sort(all(low)), sort(all(high));
	for (int i = 0; i < n; i++) {
		p1 = lower_bound(all(high), miv[i]) - high.begin();
		p2 = upper_bound(all(low), mav[i]) - low.begin();
		cout << p1 + 1 << " " << p2<< '\n';
	}
}