hyunkookim 님의 블로그

658. Find K Closest Elements 정렬된 배열에서 x에 가장 가까운 원소 k개를 찾아 정렬된 상태로 반환하는 문제입니다.✅ 핵심 아이디어배열이 정렬되어 있으므로 이분 탐색(Binary Search) 를 이용해서 빠르게 풀 수 있습니다.arr[i] ~ arr[i+k-1] 범위가 정답 후보가 되도록 슬라이딩 윈도우를 이동합니다.거리 차가 작거나, 같다면 더 작은 숫자를 우선 선택합니다.✅ 방법 1: 이분 탐색 기반 슬라이딩 윈도우 (O(log(n - k) + k))class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: # 이분 탐색으로 윈도우 시작점(start)을 ..

24. Swap Nodes in Pairs 문제의 조건:노드 값은 바꾸지 말고, 연결만 바꿔라 class Solution(object): def swapPairs(self, head: ListNode) -> ListNode: # 기저 조건: 노드가 0개이거나 1개면 그대로 리턴 if not head or not head.next: return head # 스왑 대상 노드 first_node = head second_node = head.next # 재귀 호출: 다음 노드부터 또 swapPairs 수행 first_node.next = self.swapPairs(second_node.next) ..

739. Daily Temperatures ❌ 문제점 요약temperatures 배열은 정렬되어 있지 않기 때문에, 이진 탐색 (binary search)을 사용할 수 없습니다.dfs(i+1, val) 함수는 i+1 ~ 끝까지 중 val보다 큰 수를 이진 탐색으로 찾지만, 이건 정렬된 배열에서만 유효합니다.따라서 현재 접근 방식은 잘못된 가정에 기반한 것입니다.✅ 올바른 풀이: Stack (O(n))가장 적절한 방식은 스택을 이용한 역방향 탐색입니다.class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) res = [0] * n s..

210. Course Schedule II **Topological Sort (위상 정렬)**을 이용해 해결해야 하는 그래프 문제입니다.한 문장씩 간단하게 설명해드릴게요.✅ 문제 설명 (한 문장씩 해석)There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.👉 0번부터 numCourses - 1번까지의 수업이 있으며, 총 numCourses개입니다.You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take cours..

84. Largest Rectangle in Histogram class Solution: def largestRectangleArea(self, heights: List[int]) -> int: l, r = 0, len(heights)-1 maxArea = 0 minHeap = [] while l heights[r]: r-=1 else: l+=1 return maxArea 네가 작성한 이 코드는 아이디어 자체는 괜찮아 보이지만,문제 요구사항(시간복잡도) 를 만족하지 못해서 시간초과(TLE) 가 날 가능성이 아주 높아.✨ 먼저 네 코드 흐름 요약l, r을 양쪽 끝에..

1235. Maximum Profit in Job Scheduling ✨ 문제 요약n개의 작업이 있고, 각각시작 시간 startTime[i]끝나는 시간 endTime[i]이익 profit[i]서로 겹치지 않게 작업을 선택하면서얻을 수 있는 최대 이익을 구하는 문제.✨ 핵심 풀이 아이디어이건 "배낭 문제 (Knapsack Problem)" + "이진 탐색" 조합 문제야.흐름:일들을 (start, end, profit) 튜플로 정리하고, endTime 순서대로 정렬한다.dp[i] = i번째 작업까지 고려했을 때 얻을 수 있는 최대 이익 저장.각 작업에 대해:이 일을 선택하지 않을지 (dp[i-1])이 일을 선택할지 (현재 profit + 이전에 겹치지 않는 일까지 최대 profit)둘 중 큰 걸 고른다.겹치..

146. LRU Cache evict the least recently used key제거하다, 가장 적게, 최근에, 사용된=> Least Recently Used "가장 오랫동안 안 쓴 것" 을 삭제class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.data = {} # evict the least recently used key: # 제거하다, 가장 적게, 최근에, 사용된 # Least Recently Used (가장 오랫동안 안 쓴 것) 을 삭제 self.oldest_key = [] # 가장 오래된건 self...

621. Task Scheduler 문제 설명You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n.해석:너는 CPU 작업 목록 tasks를 받는다.각각의 작업은 A~Z 중 하나의 알파벳으로 표시되어 있다.그리고 숫자 n도 함께 주어진다.Each CPU interval can be idle or allow the completion of one task.해석:CPU는 매 시간마다 하나의 작업을 할 수 있다.또는 아무 작업도 하지 않고 **idle(쉬는 상태)**일 수 있다.Tasks can be completed in any order, but there's a constraint: there h..

310. Minimum Height Trees class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: # 트리는 양방향 트리.. # 즉, 순환 구조 없으면, 트리임 # 그래서, 가장 최소 트리의 높이 adj = {} for i in range(n): adj[i] = [] for n1, n2 in edges: adj[n1].append(n2) adj[n2].append(n1) def dfs(node, i): if node not ..

438. Find All Anagrams in a String class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: # anagram: 문자 순서 다른거 # 시작점 res 에 추가 def getCHcnt(strs): cntMap = {} for s in strs: if s not in cntMap: cntMap[s] = 0 cntMap[s] += 1 cntMap = dict(sorted(cntMap.items(), key=lambda x: x[0])..