hyunkookim 님의 블로그

380. Insert Delete GetRandom O(1) https://youtu.be/j4KwhBziOpg?si=oBpHxLpob44XbDSt  O(1) 는 hashset 으로 푸는 것임index 번호를 hashset 으로.random 뽑기와 average 도 O(1)로 풀어야되므로, List도 사용해야함 class RandomizedSet: def __init__(self): self.numMap = {} # 값 -> 리스트의 인덱스를 매핑하는 딕셔너리 self.numList = [] # 실제 값들을 저장하는 리스트 def insert(self, val: int) -> bool: res = val not in self.numMap # 없으면(if..

274. H-Index  결론조건 **"인용 횟수 ≥ 논문 순위"**는 H-Index의 정의에서 나옵니다:i+1번째 논문까지는 최소 i+1번 이상 인용되었는지 확인.이 조건을 만족할 때, 해당 논문 수(i+1)가 H-Index가 됩니다.이 조건이 깨지는 순간부터는 인용 횟수가 부족하므로 H-Index로 고려할 수 없습니다. class Solution: def hIndex(self, citations: List[int]) -> int: #citations[i] >= i+1 citations.sort(reverse=True) h_score = 0 for i in range(len(citations)): if citations[i] >..

45. Jump Game II https://youtu.be/dJ7sWiOoK7g?si=bLV97rhs3OQMvktA GPT: 그리디 알고리즘으로 해결class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) jumps = 0 # 최소 점프 횟수 current_end = 0 # 현재 점프 범위 끝 farthest = 0 # 현재 범위 내에서 도달 가능한 가장 먼 위치 for i in range(n - 1): # 마지막 위치는 탐색하지 않음 # 현재 위치에서 도달 가능한 가장 먼 위치 갱신 farthest = max(farthe..

55. Jump Game https://youtu.be/Yan0cv2cLy8?si=bUQX7npOheNXftIY ✅ 풀이class Solution: def canJump(self, nums: List[int]) -> bool: # 목표 위치는 초기에는 마지막 인덱스 goal = len(nums) - 1 # 뒤에서부터 순회하며 목표 위치를 갱신 for i in range(len(nums) - 1, -1, -1): # 현재 위치에서 goal에 도달 가능하면 goal을 갱신 if i + nums[i] >= goal: goal = i # goal이 0이면 시작점에서..

121. Best Time to Buy and Sell Stock from typing import Listclass Solution: def maxProfit(self, prices: List[int]) -> int: # 초기 구매 가격을 첫 번째 날의 가격으로 설정 buy_price = prices[0] # 현재까지의 최저 구매 가격 buy_idx = 0 # 구매가 이루어진 시점의 인덱스 profit = 0 # 현재 판매에서 발생한 이익 max_profit = 0 # 최대 이익 저장 변수 # 두 번째 날부터 순회 시작 (첫 번째 날은 이미 구매 가격으로 설정됨) for i in range(1, len(..

189. Rotate Array 내 풀이class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) for i in range(0, k): tmp = nums[n-1] nums[1:] = nums[:-1] nums[0] = tmp Time Limit Exceeded 발생 Follow up:Try to come up with as many solutions as you can. There ..

169. Majority Element class Solution: def majorityElement(self, nums: List[int]) -> int: res = {} # hashmap for n in nums: if n in res: res[n]+=1 else: res[n] = 1 # 다수 요소 찾기: 빈도 값 기준으로 최대값을 가진 키 반환 return max(res, key=res.get)   Follow-up: Could you solve the problem in linear time and in O(1) space?

80. Remove Duplicates from Sorted Array II https://youtu.be/ycAq8iqh0TI?si=xnT3SvO1n9jkMNVq class Solution: def removeDuplicates(self, nums: List[int]) -> int: k = 0 # 중복되지 않은 요소를 저장할 위치를 추적하는 포인터 prev = nums[0] - 1 # 이전에 저장된 값을 추적하기 위한 변수, nums[0]보다 작은 값으로 초기화 cnt = 0 # 현재 숫자가 몇 번 등장했는지 추적 # 배열을 순회하며 중복을 제거 for i in range(len(nums)): if nums[i..

26. Remove Duplicates from Sorted Array https://youtu.be/DEJAZBq0FDA?si=xk4u4GvMAZ3J0Ljh class Solution: def removeDuplicates(self, nums: List[int]) -> int: k = 0 # 중복되지 않은 요소를 저장할 위치를 추적하는 포인터 prev = nums[0] - 1 # 이전에 저장된 값을 추적, nums[0]보다 작은 값으로 초기화 # 배열 순회 for i in range(len(nums)): if prev

27. Remove Element https://youtu.be/Pcd1ii9P9ZI?si=3UAPDn1Wa5uhGsM9 class Solution: def removeElement(self, nums: List[int], val: int) -> int: k = 0 # val이 아닌 요소를 저장할 위치를 추적하는 포인터 # nums 배열을 순회하며 val이 아닌 요소를 앞으로 이동 for l in range(len(nums)): # l: 현재 요소를 확인하기 위한 포인터 if nums[l] != val: # 현재 요소가 val과 다르면 nums[k] = nums[l] # 현재 요소를 k 위치로 이동 ..