hyunkookim 님의 블로그

68. Text Justification https://youtu.be/TzMl4Z7pVh8?si=nYIZZBc0f4565dnG class Solution: def fullJustify(self, words: List[str], maxWidth: int) -> List[str]: res = [] line, length = [], 0 i = 0 while i maxWidth: # 문장 길이를 초과함 # 새로운 단어 추가 하면, 문장 길이 초과하면 # 이 문장은 완료되었다고 보고(line complete) # 문장 내 공백 조절해야 함 extr..

28. Find the Index of the First Occurrence in a String https://youtu.be/Gjkhm1gYIMw?si=amLg-uiF5c1EAVDv class Solution: def strStr(self, haystack: str, needle: str) -> int: # needle이 빈 문자열인 경우, 요구사항에 따라 0을 반환 if needle == "": return 0 # needle이 haystack에 포함되지 않으면, 바로 -1을 반환 # 이 조건은 불필요한 반복을 줄여 효율성을 높여줌 if needle not in haystack: return ..

6. Zigzag Conversion https://youtu.be/Q2Tw6gcVEwc?si=uqM3oulxloxx3h1P class Solution: def convert(self, s: str, numRows: int) -> str: # numRows가 1인 경우 변환할 필요가 없으므로 입력 문자열 그대로 반환 if numRows == 1: return s res = "" # 변환된 결과 문자열을 저장할 변수 # 각 행(row)을 순회하며 변환된 문자열을 생성 for r in range(numRows): increment = 2 * (numRows - 1) # 각 주기에서의 문자 간격 (..

12. Integer to Roman https://youtu.be/ohBNdSJyLh8?si=WM_rDigggPqJ_-PE class Solution: def intToRoman(self, num: int) -> str: # 로마 숫자와 해당 값을 저장한 리스트 # 로마 숫자는 큰 값에서 작은 값 순으로 정렬되어 있음 symList = [["I", 1], ["IV", 4], ["V", 5], ["IX", 9], ["X", 10], ["XL", 40], ["L", 50], ["XC", 90], ["C", 100], ["CD", 400], ["D", 500], ["CM", 900], ..

42. Trapping Rain Water https://youtu.be/ZI2z5pq0TqA?si=vMNp4_SRqkju2a6b  O(n) 공간 사용from typing import Listclass Solution: def trap(self, height: List[int]) -> int: # 높이 배열의 길이를 가져옵니다. n = len(height) # 배열이 비어있는 경우 0을 반환 (예외 처리) if not n: return 0 # maxLeft: 각 위치에서 왼쪽으로 가장 높은 기둥의 높이를 저장할 리스트 # maxRight: 각 위치에서 오른쪽으로 가장 높은 기둥의 높이를 저장할 리스트 ..

14. Longest Common Prefix 내코드class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: res = "" n_strs = len(strs) cur_point = 0 min_len = min([len(s) for s in strs]) while cur_point   https://youtu.be/0sWShKIJoo4?si=XvcOnKeTitIM6Uip class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: res = "" # 결과로 반환할 가장 긴 공통 접두사를..

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는 완주 가능한 유일한 ..