[leetcode] 354. Russian Doll Envelopes

문제 : https://leetcode.com/problems/russian-doll-envelopes/

---

배열을 width 오름차순으로 정렬한다. 조건에서 width 는 고려하지 않게 하기 위함이다.

정렬 후 앞에 있는 요소의 width는 뒤에 있는 요소의 width 보다 항상 작거나 같으므로 height 만 고려하면 된다.

결국 정렬된 후 height의 LIS(최장 증가 수열)의 길이를 구하면 이게 정답이 된다.

 

위와 같은 알고리즘을 사용한다고 할 때, 고려할 점이 하나 있다.

[[4,5],[4,6],[6,7],[2,3],[1,1]]

입력 배열이 위와 같을 때, [4,5] [4,6] 중 하나만 선택되게 해야 한다.

height의 LIS로 정답을 구할 때 width가 동일한 요소들은 하나만 선택하게 하려면 증가수열이 아닌 감소수열로 만들면 된다. 즉, 동일한 width 요소들의 height들은 내림차순 정렬한다. 

입력 배열을 위와 같은 방법으로 정렬하면

[[1,1], [2,3], [4,6], [4,5], [6,7]]

가 되고 height 값들로 LIS 배열을 구해보면 

[1, 3, 6, 5, 7]   ->  [1, 3, 5, 7] or [1, 3, 6, 7] 

이 되어 정답은 4가 된다.

 

lower_bound (binary search)를 이용하여 구현하면 시간복잡도는 O(NlogN)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/354.%20Russian%20Doll%20Envelopes.cpp