Tech for good

class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k = k % n # In case k is larger than n # Step 1: Reverse the entire array nums.reverse() # Step 2: Reverse the first k elements nums[:k] = reversed(nums[:k]) # Step 3: Reverse the remaining n-k elements nums[k:] = reversed(nums[k:]) ..

class Solution: def isPrefixOfWord(self, sentence: str, searchWord: str) -> int: words = sentence.split() for i, word in enumerate(words): if word.startwith(searchword): return i+1 return -1 Explanation:Split the Sentence: The input sentence is split into a list of words using .split(), which automatically handles single spaces.Iterate Over Words..

🔹 문제 풀이 접근이 문제는 최소한의 거래로 모든 부채를 정산하는 문제이다.즉, 누가 누구에게 돈을 줘야 하는지 최소한의 거래(transactions)로 해결하는 것이 목표이다.✅ 해결 방법: Backtracking 각 사람의 최종 잔액을 계산주어진 거래를 기반으로 각 사람의 순 잔액(balance)을 계산.예를 들어, 어떤 사람이 $10 빌려줬으면 +10, $5 빌렸으면 -5.잔액이 0이 아닌 사람들을 대상으로 최소 거래 조합 찾기부채(- 잔액)와 자산(+ 잔액)을 매칭하여 최소 거래로 해결.백트래킹(Backtracking)을 활용하여 모든 가능한 거래를 탐색.from collections import defaultdictclass Solution: def minTransfers(self, tr..

https://leetcode.com/problems/median-of-two-sorted-arrays/description/ 🔹 문제 풀이 접근이 문제는 두 개의 정렬된 배열(nums1, nums2)이 주어질 때, 병합 후 중앙값(median)을 찾는 문제이다. ✅ 최적화 방법 (이진 탐색 활용)이진 탐색(Binary Search)을 사용하여 한 배열을 절반으로 분할하면서 답을 찾음.시간 복잡도: O(log(min(m, n)))class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # nums1이 항상 짧은 배열이 되도록 보장 if len(nums1) > l..

알고리즘:주어진 문자열을 파싱하여 문자 -> 빈도 형태로 해시맵에 저장해시맵의 키(문자)를 알파벳 순으로 정렬최종 결과 문자열을 생성from collections import defaultdictclass Solution: def betterCompression(self, compressed: str) -> str: freq_map = defaultdict(int) i = 0 n = len(compressed) # 문자열을 순회하면서 문자와 숫자 파싱 while i  🔹 시간 복잡도:문자열을 한 번 순회하면서 파싱 (O(N))해시맵을 정렬 (O(K log K), K는 문자 종류의 개수, 최대 26)결과 생성 (O(K))총..

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ low, mid, high = 0, 0, len(nums) - 1 # 세 개의 포인터 설정 while mid 코드 설명low, mid, high 세 개의 포인터를 사용하여 배열을 정렬한다.초기 설정low: 0을 배치할 위치mid: 현재 검사 중인 위치high: 2를 배치할 위치while 반복문 (mid ≤ high)nums[mid] == 0 (빨간색)low와 mid를 swap하고 low와 mid를 증가nums[mid..

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ non_zero_index = 0 # 배열을 처음부터 끝까지 순회하면서 0이 아닌 요소를 앞으로 이동 for i in range(len(nums)): if nums[i] != 0: # 현재 숫자(nums[i])와 non_zero_index 위치의 숫자를 스왑 nums[non_zero_index], nums[i] = nums[i..

이 문제를 한 번의 순회(One-pass)로 해결하는 방법은 두 개의 포인터(first, second)를 사용하는 것이다.first 포인터를 먼저 n칸 이동시킨 후, second 포인터를 first와 함께 이동하면 first가 끝에 도달했을 때 second는 삭제할 노드의 직전 노드를 가리키게 된다.✅ 알고리즘 풀이 (Two Pointer)더미 노드 추가: 삭제할 노드가 head일 수도 있으므로 더미 노드를 추가.first 포인터 선행 이동: first를 n칸 먼저 이동.두 포인터 이동: first가 리스트의 끝에 도달할 때까지 second와 함께 이동.노드 삭제: second.next를 second.next.next로 변경하여 노드 삭제.새로운 head 반환: dummy.next를 반환.# Defini..

해시셋(Hash Set) 활용 -중복을 방지하면서 각 노드를 탐색할 때 (k - 현재 노드 값)이 존재하는지 확인하는 방법. 설명dfs 함수를 사용하여 트리를 깊이 우선 탐색(DFS) 한다.각 노드를 방문할 때 k - node.val이 seen 집합에 존재하는지 확인한다.존재하면 True를 반환하고, 없으면 현재 노드 값을 seen에 추가한 후 왼쪽과 오른쪽 서브트리를 탐색한다.전체 탐색이 끝날 때까지 조건을 만족하는 쌍이 없으면 False를 반환한다.시간 복잡도각 노드를 한 번씩 방문하므로 O(N) (N은 트리의 노드 개수).공간 복잡도최악의 경우 모든 노드 값을 seen에 저장해야 하므로 O(N). # Definition for a binary tree node.class TreeNode: de..

Two Pointer 방식으로 해결하는 방법Two Pointer 방식을 사용하려면, BST(Binary Search Tree)의 중위 순회(in-order traversal)를 수행하여 오름차순으로 정렬된 리스트를 만든 후, 투 포인터를 사용하여 두 숫자의 합이 k가 되는지 확인하면 된다.Two Pointer 알고리즘BST를 중위 순회하여 정렬된 리스트를 생성중위 순회(In-order Traversal)를 수행하면 BST의 값이 오름차순으로 정렬됨.Two Pointer 기법을 활용하여 합이 k가 되는 두 수 찾기리스트의 left(처음)과 right(끝) 포인터를 설정.두 값의 합이 k보다 작으면 left를 증가.두 값의 합이 k보다 크면 right를 감소.두 값의 합이 k이면 True 반환.# Defin..