[leetcode][870] Advantage Shuffle

문제 : leetcode.com/problems/advantage-shuffle/

---

길이가 같은 정수 배열 A, B이 주어질 때, A의 원소의 순서를 변경하여 A[i] > B[i]인 원소의 개수가 최대가 되는 수열 A를 구하여라.

---

기본 아이디어는 A[i] > B[i] (조건)를 만들 수 있는 A[i] 값은 A 원소가 클수록 조건을 만족할 가능성이 높으며 A 원소가 작을수록 조건을 만족할 가능성이 낮다. 즉, 큰 원소값이 조건을 만족할 수 없으면 이는 작은 원소값도 만족할 수 없다.

따라서 큰 원소값을 세팅할 수 있는 곳에 먼저 세팅하고, 큰 원소값을 사용할 수 없는 곳은 버리는 수로 작은 원소값으로 대체한다.

 

A 배열을 오름차순 정렬하고, B 배열을 {원소값, 인덱스} 배열로 변경하여 이를 오름차순 정렬한다.

A배열의 앞에서부터 탐색하는 left 인덱스(0부터 시작), 뒤에서부터 탐색하는 right 인덱스(|A|-1 부터 시작) 변수를 지정한다. left 인덱스는 배열 A의 가장 작은수부터 오름차순으로 가리키며, right 인덱스는 배열 A의 가장 큰 수부터 내림차순으로 가리킨다.

 

B 배열을 뒤에서부터 탐색하면서(B배열의 큰 수부터 탐색), 탐색중인 B 인덱스를 i라 하자.

만약 A[right] > B[i].원소값 이라면 조건을 만족시킬 수 있으므로 answer[B[i].인덱스]에 A[right]를 세팅하고 right = right-1 로 갱신한다.

만일 A[right] <= B[i].원소값 이라면 조건을 만족시킬 수 없으므로 버림수인 A[left]를 answer[B[i].인덱스]에 세팅한 후 left = left + 1로 갱신하다.

 

if(A[right] > sortedB[i].first) { answer[sortedB[i].second] = A[right--]; }
else { answer[sortedB[i].second] = A[left++]; }

 

시간복잡도는 정렬하는데 드는 시간인 O(NlogN).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/870.%20Advantage%20Shuffle.cpp