LeetCode 2196 Create Binary Tree From Descriptions 접근 map의 key에 node.val, value에 node reference 가 담긴다. 부모 노드는 p[child] = parent 의 방식으로 저장하여 루트를 찾는다. descriptions 를 훑으며 map 에 이미 저장된 child 가 있다면 해당 child 를 적절한 left or right 에 연결하고, child 가 map 에 없다면 새로운 노드를 만들어 연결한다. 사고 리스트로 풀어도 되고, 맵으로 풀어도 된다. 공간 덜 쓰고 root 찾는 방법이 있을것도 같다. map 을 안쓰고는 (node 들의 reference 를 다 붙잡고 있지 않고는) tree 만들 방법이 없는거겠지? ...
LeetCode 1011, Capacity To Ship Packages Within D Days 접근 binary-search 로 적절한 배의 weight 용량을 찾는다. 처음 lo, hi 는 max(weights), sum(weight) 이다. 각각 용량에서 옮기는데 걸리는 날짜를 계산해서, 총 날짜보다 적은 시간으로 옮겼으면 lower bound 를 올리고 아니라면 upper bound를 내린다. 사고 릿코드에 binary search 문제 정말 많다. 기본적으로 이런 유형의 최적값 찾기 binary search 는 lower, upper bound 사이에 조건 충족하는 값이 1개 이상 있다고 전제한다. 조건 days 가 5라면 직관적으로 5를 다 써서 옮기는 수 중에 최적이 있을거 같아보인다. 하지만 4일이나 3일만에 옮기고 그때의 배 용량이 최적일수도 있다. 어쨌거나 우리는 최소 날짜를 구하는게 아니라 최소 용량을 구하는거라 과정을 들여다보면 binary search 가 정말 아름답게 그 값을 찾는다는 것을 알 수 있다.. 문제의 조건을 차근차근 이해함에 따라 binary search 로 뭘 찾을지, bound 는 무엇이고 어떤 경우에 bound 를 어떻게 수정할지도 보인다. ...
접근 주어진 문자열의 각 문자를 결과 문자열(ans)에 추가한다. 만약 ans[-1] 이 폭발 문자열의 마지막 bomb[-1] 과 같다면 ans[-len(bomb):] 과 bomb[:] 을 비교하여 같으면 폭발시킨다. 사고 worst case time complexity 가 10**6 이길래 O(n) 으로 되는 문제인가 고민했다. 넉넉히 된다. 조건을 이해했을때 ‘모든 폭발 문자열이 폭발하고 새로운 문자열이 생긴다’ 여서 폭발 문자열을 발견할때마다 폭발하는거랑 결과가 혹시 다른가 고민해보았다. 반례가 떠오르지 않아 O(n) 스택으로 풀었다. 한가지 처음에 arr = arr[0:arr - len(bomb)] 이렇게 넣었다가 TLE 떴다. 저렇게 넣어도 파이썬이 optimization 하지 않을까 했는데 정직하게 주어진 인덱스만큼 복사하는것 같다. pop으로 뒤에 있는 문자열을 날리는 방법으로 풀어야 한다. ...