Tech for good

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: if not root: return 0 total = 0 # 왼쪽 자식이 리프 노드라면 값 추가 if root.left and not root.left.l..

// 1. nums[l] % 2 == 0 -> left pointer가 가리키는 숫자가 짝수니?nums = [3,2,5,4]// For all indices i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2nums = [3,2,5,4]// -> [l, r-1] 범위 사이에 짝수랑 홀수가 번갈아가면서 나오니?i = 0 -> nums[i=0] = 3 -> 3 % 2 = 1i = 1 -> nums[i+1] = 2 -> 2 % 2 = 05 -> ... % 2 = 14 -> ... % 2 = 0// For all indices i in the range [l, r], nums[i]  윈도우의 시작점 찾기nums[l]이 짝수(% 2 == 0)이고, nums[l]..

슬라이딩 윈도우 반복 (for right in range(len(nums)))right 포인터를 이동하면서 새로운 숫자를 곱함.product *= nums[right] → 현재 부분 배열의 곱을 업데이트.조건을 만족하지 않으면 left 이동 (while product >= k)곱이 k 이상이면 left 포인터를 오른쪽으로 이동하여 곱을 줄임.product //= nums[left]: left가 가리키던 값을 나누어 곱을 감소.//= : 몫을 구하는 나눗셈 후 할당 연산자ex) a //= b -> a = a // bleft += 1: left를 이동하여 윈도우 크기를 줄임.가능한 부분 배열 개수 추가 (count += right - left + 1)(right - left + 1)는 현재 윈도우에서 만들 ..

class Solution: def countGoodSubstrings(s: str) -> int: count = 0 for i in range(len(s) - 2): # 길이가 3인 모든 부분 문자열을 검사 substring = s[i:i+3] # 길이 3의 부분 문자열 추출 if len(set(substring)) == 3: # 중복 문자가 없는지 확인 count += 1 return countset() => 중복을 허용하지 않는 집합(set) 자료형을 생성하는 함수중복 제거: 리스트나 문자열 등의 중복된 요소를 자동으로 제거.순서 없음: 요소의 순서가 보장되지 않음.빠른 멤버십 테스트 ..

🔍 슬라이딩 윈도우(Sliding Window)배열에서 부분 합을 효율적으로 계산하는 기법매번 전체 합을 다시 계산하지 않고, 최초 윈도우의 합을 미리 계산해둔 후 기존 윈도우의 값을 조금씩 변경하면서 업데이트한다.즉, 현재 합에서 빠질 값과 추가할 값만 업데이트하면 O(1) 시간에 갱신이 가능한 효율적 알고리즘이다! class Solution: def decrypt(self, code: List[int], k: int) -> List[int]: n = len(code) # 원래 코드 배열의 길이 # k가 0이면 모든 원소를 0으로 변경 if k == 0: return [0] * n # Extend..

// calories = [1,2,3,4,5]// k = 2// lower = 5// upper = 6// 1st: (1,2) = 3 -1// 2nd: (2,3) = 5 -> 0슬라이딩 윈도우 접근법:슬라이딩 윈도우를 사용하면 매번 k 길이의 구간을 합산하는 대신, 윈도우를 한 칸씩 이동하며 기존 합에서 가장 왼쪽 값을 빼고, 새롭게 들어온 값을 더하는 방식으로 효율적으로 합계를 구할 수 있다.시간 복잡도는 O(n)으로, calories 길이가 최대 10^5까지 가능하므로 효율적으로 동작한다.class Solution: def dietPlanPerformance(self, calories: List[int], k: int, lower:int, upper: int) -> int: points = ..

슬라이딩 윈도우(Sliding Window): 윈도우(특정 범위)가 있을 때, 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘.class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: # 초기 윈도우 설정 (첫 k개의 합) current_sum = sum(nums[:k]) max_sum = current_sum # 슬라이딩 윈도우 이동 for i in range(k, len(nums)): current_sum += nums[i] - nums[i - k] # 윈도우 이동 (새로운 값 추가, 오래된 값 제거) m..

첫번째 방법 - 해시맵(HashMap)class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: index_map = {} # 숫자의 마지막 등장 인덱스를 저장할 딕셔너리 for i, num in enumerate(nums): if num in index_map and i - index_map[num] 딕셔너리(HashMap)을 사용하여 숫자의 인덱스를 저장하고, 현재 인덱스와 이전에 나온 동일 숫자의 인덱스 차이가 k 이하인지 확인하는 방식.풀이 설명index_map 딕셔너리를 사용하여 숫자 num의 가장 최근 인덱스를 저장한다.리스트 nums를 순회하면서:현재..

Two Pointers Approach (O(n) 시간, O(1) 공간)뒤에서부터 문자열을 처리하면서 '#'을 만나면 백스페이스를 적용한다.각 문자열에 대해 유효한 문자 위치를 찾아 비교한다.포인터를 이동하면서 문자 비교를 진행한다.class Solution: def backspaceCompare(self, s: str, t: str) -> bool: # 두 개의 포인터를 각각 문자열 s와 t의 끝에서 시작 i, j = len(s) - 1, len(t) - 1 # 백스페이스('#')의 개수를 추적하는 변수 back_s, back_t = 0, 0 # 두 문자열 중 하나라도 아직 탐색할 문자가 남아있는 동안 반복 whil..

첫번째 방법class Solution: def canMakeSubsequence(self, str1: str, str2: str) -> bool: i, j = 0, 0 # 두 문자열을 비교할 포인터 while i 코드 설명투 포인터 접근법 (i, j 사용)i: str1을 탐색하는 포인터j: str2를 탐색하는 포인터문자 비교str1[i] == str2[j]: 그대로 유지 가능str1[i]가 str2[j]의 바로 이전 문자인지 확인(ord(str1[i]) - ord('a') + 1) % 26 + ord('a') == ord(str2[j])이 조건이 참이면 str1[i]를 변환하여 str2[j]로 만들 수 있음.26이 나오는 이유는 알파벳이 26개 존재하기 때문..