hyunkookim 님의 블로그

724. Find Pivot Index 1) Prefix Sums 누적합 이용 풀이 방법class Solution: def pivotIndex(self, nums: List[int]) -> int: # 자신을 제외한 왼쪽 합 == 오른쪽 합이 되는 pivot index를 찾는 문제 total = 0 # 전체 합을 계산하기 위한 변수 PrefixSum = [] # 0번 인덱스부터의 누적합 배열 for n in nums: total += n # 현재까지의 누적합을 계산 PrefixSum.append(total) # 누적합을 배열..

75. Sort Colors  class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # We will use the integers 0, 1, and 2 rgb = [0, 0, 0] for n in nums: rgb[n] += 1 i = 0 for n in range(len(rgb)): for _ in range(rgb[n]): nums[i] = n ..

215. Kth Largest Element in an Array class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # minheap 으로 만들고, k개 까지. 힙 개수 유지하게 하면, # k 개 보다 많으면 작은 것들 제거 # 그렇게 하면, minheap[0]에는 k번째 큰 것이 남아있음 heapq.heapify(nums) while( len(nums) > k): heapq.heappop(nums) return nums[0] 메모리 절약을 위해, k 개 만큼 우선 넣어서, minheap 만들고.1개씩 추가해서, k개 넘는..

746. Min Cost Climbing Stairs class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: cost.append(0) for i in range(len(cost)-1-2, -1, -1): cost[i] += min(cost[i+1], cost[i+2]) return min(cost[0], cost[1]) https://youtu.be/ktmzAZWkEZ0?si=ovGzSVLU3LhGRQGh class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # 꼭대기를 0..

1137. N-th Tribonacci Number 내 풀이 class Solution: def tribonacci(self, n: int) -> int: T = [0] * 38 T[0] = 0 T[1] = 1 T[2] = 1 if n>2: for nn in range(3, n+1): T[nn] = T[nn-3]+T[nn-2]+T[nn-1] return T[n] 솔루션class Solution: def tribonacci(self, n: int) -> int: arr = [0, 1, 1] if n  3차: 2025.01.02(목): 해결함class ..

17. Letter Combinations of a Phone Number GPT: 백트레킹class Solution: def letterCombinations(self, digits: str) -> List[str]: # 1. 숫자와 문자 매핑 정의 phone_map = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } # 2. 결과 리스트 초기화 res = [] # 3. 입력이 빈 문자열인 경우 빈 리스트 반환 i..

875. Koko Eating Bananas https://youtu.be/U2SozAs9RzA?si=lxNzqfZ1jL_lzHUX from math import ceilfrom typing import Listclass Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: # 이진 탐색 범위 설정 # 최소 속도는 1 (최소 한 개라도 먹음), 최대 속도는 max(piles) (한 번에 가장 큰 더미를 모두 먹음) # Set the binary search range: # Minimum speed is 1 (at least one banana per hour), and maximu..

2300. Successful Pairs of Spells and Potions https://youtu.be/OKnm5oyAhWg?si=k_d-0f6Nt10xOCD6 class Solution: def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]: # spell * potion >= success 를 만족하는 쌍을 찾아야 함 # 이를 변형하면: potion >= success / spell 이 됨 # 즉, potion의 값이 특정 기준값 이상인 경우를 찾아야 함. # 1. potions 리스트를 정렬하여 이진 탐색을 수행 가능하도록 준비..

374. Guess Number Higher or Lower # The guess API is already defined for you.# @param num, your guess# @return -1 if num is higher than the picked number# 1 if num is lower than the picked number# otherwise return 0# def guess(num: int) -> int:class Solution: def guessNumber(self, n: int) -> int: l, r = 1, n while l mid pick => pick  https://youtu.be/x..

994. Rotting Oranges https://youtu.be/y_2x5llfqsE?si=ZrbbbsMQwGQ7Gt-o from collections import dequefrom typing import Listclass Solution: def orangesRotting(self, grid: List[List[int]]) -> int: fresh = set() # 신선한 오렌지 좌표를 저장 rotten = deque() # 썩은 오렌지 좌표를 저장 directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 4방향 이동 rows, cols = len(grid), len(grid[0]) # 1. ..