# [Gold IV] Scrambled Letters [문제 링크](https://www.acmicpc.net/problem/5867) ## 문제 설명 <p>Farmer John keeps an alphabetically-ordered list of his N cows (1 <= N <= 50,000) taped to the barn door. Each cow name is represented by a distinct string of between 1 and 20 lower-case characters.</p><p>Always the troublemaker, Bessie the cow alters the list by re-ordering the cows on the list. In addition, she also scrambles the letters in each cow's name. Given this modified list, please help Farmer John compute, for each entry in the list, the lowest and highest positions at which it could have possibly appeared in the original list.</p> ## 입력 <ul><li>Line 1: A single integer N.</li><li>Lines 2..1+N: Each of these lines contains the re-ordered name of some cow.</li></ul> ## 출력 <ul><li>Lines 1..N: Line i should specify, for input string i, the lowest and highest positions in Farmer John's original list the original version of string i could have possibly appeared.</li></ul> ## 풀이 다른 문자열들을 greater로 정렬한 후 less 문자열로 이분 탐색, 다른 문자열들을 less로 정렬한 후 greater 문자열로 이분 탐색으로 두 값을 찾았다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<string> v(n); for(int i=0;i<n;i++) cin >> v[i]; vector<string> small = v; for(int i=0;i<n;i++) sort(small[i].begin(), small[i].end()); sort(small.begin(), small.end()); vector<string> big = v; for(int i=0;i<n;i++) sort(big[i].begin(), big[i].end(), greater<char>()); sort(big.begin(), big.end()); for(int i=0;i<n;i++) { string smallS=v[i], bigS=v[i]; sort(smallS.begin(), smallS.end()); sort(bigS.begin(), bigS.end(), greater<char>()); int a = upper_bound(big.begin(), big.end(), smallS) - big.begin(); int b = upper_bound(small.begin(), small.end(), bigS) - small.begin(); if(smallS!=bigS) a++; cout << a << ' ' << b << '\n'; } } ```