Tech for good

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개 존재하기 때문..

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

https://neetcode.io/problems/is-palindrome NeetCode neetcode.io첫번째 방법 - String Manipulationclass Solution: def isPalindrome(self, s: str) -> bool: # 1. 알파벳과 숫자만 남기고 소문자로 변환 filtered_s = ''.join(c.lower() for c in s if c.isalnum()) # 2. 문자열을 뒤집어서 원래 문자열과 비교 return filtered_s == filtered_s[::-1]isalnum() -> 문자열이 문자 혹은 숫자로 되어있으면 참 리턴, 아니면 거짓 리턴시간 복잡도문자열 필터링: O..

첫번째 방법 (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) # 주어진 배열의 길이..

풀이1) set  자료구조 사용class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1) & set(nums2))시간 복잡도 분석set(nums1): O(N)set(nums2): O(M)set1 & set2: O(min(N, M))list(...): O(K) (교집합 원소 수를 K라고 가정)➡️ 최종 시간 복잡도: O(N + M) (매우 효율적)풀이2) two-pointer 사용class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: ..

class Solution: def isSubsequence(self, s: str, t: str) -> bool: i, j = 0, 0 # Pointers for s and t while i i += 1 -> s의 인덱스를 증가j += 1 -> s와 상관없이 (즉, 매치됨과 상관없이) t의 인덱스를 하나씩 증가 Example 2의 경우, x가 t에 없으므로 i False시간 복잡도 및 공간 복잡도시간 복잡도: O(n) (t의 길이만큼 한 번 순회)공간 복잡도: O(1) (추가적인 공간 사용 없음)

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