Tech for good

슬라이딩 윈도우 반복 (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)는 현재 윈도우에서 만들 ..

🔍 슬라이딩 윈도우(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 reverseVowels(self, s: str) -> str: left, right = 0, len(s) - 1 vowels = set('aeiouAEIOU') # 대소문자 모두 포함된 집합 s = list(s) # 문자열을 리스트로 변환 (문자 교환을 위해) while left 주요 사항: in 연산자 사용s[left] in vowels를 사용.대소문자 포함된 set 사용set('aeiouAEIOU')를 사용하여 in 연산을 빠르게 수행.set은 해시 테이블을 기반으로 동작하므로, 요소가 존재하는지 확인하는 연산(in 연산자)이 평균적으로 O(1) (상수 시간)에 수행.반면, list나 tup..

첫번째 방법 (Two-Pointer + Queue = Greedy)(1) Two-Pointer 두 개의 리스트 (positives, negatives)를 따로 저장한 후, 두 개의 포인터를 이용하여 한 번에 두 리스트를 합치는 방식 차용.여기서 zip(positives, negatives)를 사용하여 두 리스트를 같은 인덱스에서 번갈아가며 가져오는 방식을 적용.(2) Queue Python의 리스트 (list)를 Queue처럼 사용하여 양수와 음수를 저장했다가 순차적으로 가져와서 최종 리스트를 생성하는 방식.positives.append(num) 및 negatives.append(num) 연산은 O(1) 이므로 효율적임.여기서 zip(positives, negatives)를 사용하여 두 리스트를 같은 인..

📌 코드 설명: 문자열 압축 알고리즘이 코드는 연속된 문자를 압축하여 원래 배열을 수정하는 문제를 해결한다.🛠 코드의 핵심 개념투 포인터(Two-Pointer) 기법 사용i → 원본 문자열을 읽어가는 포인터write → 압축된 문자열을 저장하는 포인터반복문을 사용해 같은 문자가 연속되는 그룹을 찾고, 압축하여 저장그룹의 길이가 1이면 문자만 저장그룹의 길이가 2 이상이면 "문자 + 숫자(횟수)" 형태로 저장class Solution: def compress(self, chars: List[str]) -> int: write = 0 # 압축된 결과를 저장할 위치 i = 0 # 원본 배열을 탐색하는 위치 while i 1: for..

해결 방법: 투 포인터(Two Pointers)이 문제를 O(n log n) 정렬로 해결하는 것은 쉽지만, O(n) 시간 복잡도로 해결하려면 투 포인터(Two Pointers) 기법을 사용해야 한다.핵심 아이디어음수가 포함된 정렬된 배열에서, 가장 큰 제곱값은 절댓값이 가장 큰 수에서 나온다.배열에서 절댓값이 가장 큰 숫자는 양쪽 끝에 위치해 있다. (가장 작은 수는 음수이고, 가장 큰 수는 양수이므로)왼쪽(left)과 오른쪽(right)에서 시작하는 두 개의 포인터를 사용하여 가장 큰 제곱값을 뒤에서부터 채운다.class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) # 주어진 배열의 길이..