Sorting 유형의 문제를 찾아보던중 꽤 재밌어 보인다고 생각했던 문제여서 풀어보았다. 일단 내가 처음 이 문제르 봤을때 들었던 생각은 좀 많이 까다로웠다. nums1의 permutation 값에서 nums2에 있는 원소들을 비교했을때 가장 큰 원소를 얻을수있는 조합을 리턴해야 하는 문제였다.
솔직히 그냥 nums1을 가지고 permutation 을 만들어서 하나 하나 비교하는 방법도 있었겠지만 그러기에는 테스트 케이스가 너무나도 컸기때문에 이것은 단순한 sorting 방법으로 풀수밖에 없었다.
이 문제는 Greedy 하게 푸는게 중요한데 nums1에 있는 원소가 더 크다고 무작정 넣는게 아닌, 아슬아슬 하게 큰 원소들만 넣어야한다는 점이 greedy 하게 만든거같다.
그리고 내가 참고 했던 풀이에서는 nums2에 있는 index 오더를 그대로 따르되, nums2를 가장 큰 숫자로 정렬한거 마냥 만들어주었다. 그리고 nums1에서도 큰 숫자로 정렬 해준뒤에 만약 nums1의 정렬된 순서대로 left 와 right을 이용해서 가장 큰 숫자에는 가장 큰 숫자로 상대해주고, 그 숫자가 없다면 가장 작은 숫자를 사용하는 등의 방식을 이용해주었다.
물론 이런 방법대로 문제를 풀수도 있었지만, 사실 더 간단한 방법은 multiset 과 upper_bound 함수를 쓰는 방법이었던거 같다. multiset 을 쓴 이뉴는 중복된 원소를 넣어 주기 위함이었고 erase 가 쉽기때문에 써준거같다.
다른 사람의 풀이. 훨씬 더 이해가 가기 쉽고 이런 방식으로 생각했다면 나중에 비슷한 유형의 문제가 나와도 풀수있을거같다.
배운점:
- Multiset 의 활용
- Upper_bound 의 활용
