[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가 동일한 요소들은 하나만 선택하게 하려..
2022. 5. 26.
[Leetcode] 31. Next Permutation
문제 : https://leetcode.com/problems/next-permutation/ 정수 배열이 있을 때 해당 배열의 요소들의 순서를 바꿔서 사전순 다음 시퀀스로 만들어라. 만일 불가능하다면 사전순 가장 작은 순서로 재배열해야한다. 예를 들어, arr = [2, 1, 3]이라면 사전순 다음 순서인 [2, 3, 1]로 재배열 시켜야한다. 전부 내림차순으로 정렬된 순열의 다음 사전순 배열은 이들을 역순한 것과 같다. 예를 들어, arr = [3, 2, 1]의 경우 다음 사전순 배열은 [1, 2, 3]이다. 내림차순된 배열의 다음 사전순 배열을 구하는 방법을 알았으니 내림차순 배열의 가장 앞에 있는 숫자를 해당 숫자보다 큰 수들보다 가장 작은 수로 바꾸면 다음 사전순 배열을 구할 수 있다. 말이 좀..
2022. 4. 3.