문제

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

문제 접근 및 풀이

• 처음에 그냥 width로 sort해서 각 width당 제일 작은 것들로만 넣어주면 된다고 생각했음
• 이렇게 하면 height이 max값이어도 width가 작다는 이유로 그 안에 봉투를 넣어주게 됨
• 적절한 풀이 방법이 아님 - 탐욕법의 느낌(?)
• 결국 여기저기서 정답을 보고 이해했음

결과

function maxEnvelopes(envelopes) {
  envelopes.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
  let memo = [];
  for (let i = 0; i < envelopes.length; i++) {
    let height = envelopes[i][1];
    let left = 0;
    let right = memo.length;
    while (left < right) {
      let mid = (left + right) >> 1;
      if (memo[mid] < height) left = mid + 1;
      else right = mid;
    }
    memo[left] = height;
  }
  return memo.length;
}

width 오름차순, 같다면 height 내림차순으로 정렬
memo 배열을 생성
요소 하나씩 돌면서 memo에 들어갈 수 있는 요소를 탐색함
이진탐색의 개념을 이용해서 left와 right 값을 저장하여(up&down 게임처럼)
memo에 저장할 수 있는 수를 탐색
	중간 값을 기준으로 계속해서 반씩 탐색한다.
담을 수 있는 봉투를 담아둔 배열의 length를 return 한다.