hash table (2) 썸네일형 리스트형 [LeetCode/Easy] 1. Two Sum 1. Two Sum Testcase 통과한다고 해서 Submit 하면 안 된다 ㅠㅠ 제한시간 내에 Edge case를 생각해보고 그마저도 통과하면 Submit 하자! 내 풀이 vs. 답안 풀이 내 풀이 답안 풀이 $O(n^2)$보다 적은 Time complexity를 고려한 구현 for문 2개 하면 $O(n^2)$이 나오니 조합(combination)으로 먼저 구해야겠다 생각했지만 결국은 for문에 while문으로 구현함으로써 $O(n^2)$이 됨.. -> 내 풀이의 time complexity 구하는 연습을 많이 해야겠다. Hash Table 내가 필요한 건 index고 알고 있는 건 숫자이므로 key는 nums 원소, value는 index여야 함. -> 내가 필요한게 뭐고 알고 있는게 뭔지 잘 정의.. [LeetCode/Medium] 146. LRU Cache 146. LRU Cache 내 풀이 vs. 답안 풀이 내 풀이 답안 풀이 LRU cache 구현하는 data structure (단, get()과 put()의 시간 복잡도가 $O(1)$이어야 함) Dictionary Dictionary & Double Linked List cf) Key를 가진 Double Linked List는 시간 복잡도가 항상 $O(1)$ Edge case (list is empty and capacity is 1) 생각지도 못한 케이스라 방어로직 만들지 않음 head와 tail에 대한 dummy 노드 생성 Least Recently Used (LRU)에 대한 이해 least랑 latest 헷갈려서 가장 최근에 사용한 key를 삭제해야 한다고 생각함.. ah... 가장 오래 사용하지.. 이전 1 다음
