Dictionary

접근 dictionary 에 키에 해당하는 리스트를 만들고 오름차순의 input 을 받는다. get 부를때 해당 키의 리스트에서 binary search 로 최댓값을 찾는다. 사고 평범한 binary search 문제이다. 문제 조건에서 들어오는 timestamp 는 오름차순으로 찍힌다고 하는게 큰 길잡이이다. from collections import defaultdict class TimeMap: dic = None def __init__(self): self.dic = defaultdict(list) def set(self, key: str, value: str, timestamp: int) -> None: self.dic[key].append([timestamp, value]) def get(self, key: str, timestamp: int) -> str: lo, hi = 0, len(self.dic) - 1 ans = "" while lo <= hi: mid = (lo + hi) // 2 if self.dic[key][mid][0] > timestamp: hi = mid - 1 else: ans = self.dic[key][mid][1] lo = mid + 1 return ans

접근, 사고 확실히 푼 문제 수가 쌓일수록 유형별로 나눠서 생각하기가 수월한것 같다. 이 유형의 베이스는 Two Sum 이다 (무려 리트코드의 첫번째 문제!!). 배열을 탐색하며 두 개의 합의 target 이 되는 쌍을 찾는 문제인데 해쉬를 이용해 한 번 linear 로 훑는 것으로 풀 수 있다. 대략적인 풀이과정은 set 선언 배열 지나가며 각각 원소 i에 대해 target - i 가 set 에 있으면 해당 쌍 리턴, 없으면 set.add(i) 해준다. 본 문제도 이와 크게 다르지 않다. ...