hyunkookim 님의 블로그

58. Length of Last Word class Solution: def lengthOfLastWord(self, s: str) -> int: s = s.split() print(s) return len(s[-1]) https://youtu.be/KT9rltZTybQ?si=AKza_HicFcCAXSX3 class Solution: def lengthOfLastWord(self, s: str) -> int: # 문자열 s의 끝에서부터 공백이 아닌 문자를 찾아서 마지막 단어의 길이를 계산합니다. i, length = len(s) - 1, 0 # i는 문자열의 마지막 인덱스부터 시작하고, length는 마지막 단어의..

13. Roman to Integer https://youtu.be/3jdxYj3DD98?si=pX_3Vi70eTn0JF7N class Solution: def romanToInt(self, s: str) -> int: # 로마 숫자 기호를 정수로 매핑한 딕셔너리 symbols = { 'I': 1, # 1 'V': 5, # 5 'X': 10, # 10 'L': 50, # 50 'C': 100,# 100 'D': 500,# 500 'M': 1000# 1000 } res = 0 # 결과 값 저장할 ..

class Solution: def candy(self, ratings: List[int]) -> int: n = len(ratings) # 아이들의 수 res = [1] * n # 각 아이에게 최소 1개의 사탕을 할당 # 1단계: 왼쪽에서 오른쪽으로 순회하며 사탕 배분 for i in range(1, n): # 두 번째 아이부터 시작 (인덱스 1) if ratings[i - 1] ratings[i + 1]: # 현재 아이의 점수가 오른쪽 아이보다 높다면 # 현재 할당된 사탕 수와 (오른쪽 아이 사탕 + 1) 중 더 큰 값을 선택 res[i] = max(res[i], ..

134. Gas Station https://youtu.be/lJwbPZGo05A?si=AM0Po-ey6yqofKrNclass Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas)  추가 검증 코드가 필요 없다고 함.!! 추가 검증 코드 없이 왜 충분한가?1. res는 가능한 시작점으로 보장됨루프에서 total이 음수가 되는 순간 이전 주유소들(인덱스 0부터 i)에서 출발하면 연료가 부족하다는 것을 알고, 다음 주유소(i + 1)를 새로운 시작점으로 갱신합니다.이후 남은 루프는 res부터 끝까지 연료를 계산하며, 전체적으로 충분한 연료가 보장되므로 res는 완주 가능한 유일한 ..

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이면 시작점에서 도달 ..

122. Best Time to Buy and Sell Stock II https://youtu.be/3SJ3pUkPQMc?si=lGgpC5TAjAvrsyYM class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): # 상승 구간에서만 매수-매도 if prices[i] > prices[i - 1]: profit += prices[i] - prices[i - 1] return profit 그런데, prices[i] > prices[i-1] 보면, 하루 건너서만 이익 계..

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(..