투포인터

문제 설명 9093번: 단어 뒤집기 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 String Compression - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 K-diff Pairs in an Array - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Trapping Rain Water - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Remove Duplicates from Sorted Array - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Valid Palindrome - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Longest Substring Without Repeating Characters - LeetCode 주어진 문자열 s에서 중복 문자가 없는 가장 긴 부분 문자열(substring) 의 길이를 반환하는 문제입니다. ✅ 부분 문자열(Substring) 조건: 연속된 문자만 포함해야 함 (순서를 바꾸면 안 됨) 중복 문자가 없어야 함 최대 길이를 반환 해설 1️⃣ 브루트포스 (O(N²)) - 비효율적 모든 가능한 부분 문자열을 생성하여 중복이 없는지 검사 → O(N²) 비효율적이므로 사용하지 않음 2️⃣ 투 포인터 + 해시셋 (슬라이딩 윈도우, O(N)) [추천] 해시셋(Set) 을 사용하여 중복 여부를 빠르게 검사 두 개의 포인터 (left, right) 를 사용하여 윈도우 크기를 조절 시간 복잡도: O(N) (각 문자를 한 번씩만 처리) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def lengthOfLongestSubstring(s: str) -> int: char_set = set() # 중복 문자를 빠르게 찾기 위한 해시셋 left = 0 # 윈도우의 왼쪽 포인터 max_length = 0 # 최대 길이 저장 for right in range(len(s)): # 오른쪽 포인터 이동 while s[right] in char_set: # 중복 문자가 있으면 왼쪽 포인터 이동 char_set.remove(s[left]) left += 1 char_set.add(s[right]) # 새로운 문자 추가 max_length = max(max_length, right - left + 1) # 최대 길이 갱신 return max_length Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var lengthOfLongestSubstring = function(s) { let charSet = new Set(); // 중복 확인을 위한 해시셋 let left = 0; // 윈도우의 왼쪽 포인터 let maxLength = 0; // 최대 길이 저장 for (let right = 0; right < s.length; right++) { // 오른쪽 포인터 이동 while (charSet.has(s[right])) { // 중복 발생 시 왼쪽 포인터 이동 charSet.delete(s[left]); left++; } charSet.add(s[right]); // 새로운 문자 추가 maxLength = Math.max(maxLength, right - left + 1); // 최대 길이 갱신 } return maxLength; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Merge Sorted Array - LeetCode 해설 문제의 핵심 요구사항: 정렬된 두 배열 nums1과 nums2를 병합해야 합니다. nums1 배열의 길이는 m + n이며, 처음 m개의 요소만 유효한 값이고 나머지는 0으로 채워져 있습니다. 결과는 새로운 배열을 반환하는 것이 아니라 nums1 배열 자체를 수정해야 합니다. 최종 결과는 오름차순으로 정렬되어야 합니다. 이 문제를 해결하기 위한 가장 효율적인 접근 방법은 뒤에서부터 배열을 채워나가는 것입니다. 그 이유는: nums1의 뒷부분은 0으로 채워져 있어서 덮어쓸 수 있습니다. 두 배열이 이미 정렬되어 있으므로, 각 배열의 가장 큰 값부터 비교하여 더 큰 값을 nums1의 뒤에서부터 채워넣을 수 있습니다. 이 방식을 사용하면 추가적인 공간이 필요하지 않습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Step 1: 마지막 위치(5)부터 시작 비교: 3 vs 6 → 6이 더 큼 nums1 = [1,2,3,0,0,6] Step 2: 다음 위치(4) 비교: 3 vs 5 → 5가 더 큼 nums1 = [1,2,3,0,5,6] Step 3: 다음 위치(3) 비교: 3 vs 2 → 3이 더 큼 nums1 = [1,2,3,3,5,6] Step 4: 다음 위치(2) 비교: 2 vs 2 → 같음 nums1 = [1,2,2,3,5,6] …계속 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # 포인터 초기화: p1은 nums1의 마지막 실제 요소, p2는 nums2의 마지막 요소 p1 = m - 1 p2 = n - 1 # p는 nums1의 마지막 위치 p = m + n - 1 # 뒤에서부터 큰 값을 채워넣기 while p2 >= 0: # nums2의 모든 요소를 처리할 때까지 # nums1의 현재 요소가 더 크고, 아직 처리할 요소가 남아있다면 if p1 >= 0 and nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 # nums2의 현재 요소가 더 크거나, nums1의 처리할 요소가 없다면 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ function merge(nums1, m, nums2, n) { // 각 배열의 마지막 요소부터 시작하는 포인터 설정 let p1 = m - 1; // nums1의 실제 마지막 요소 위치 let p2 = n - 1; // nums2의 마지막 요소 위치 let p = m + n - 1; // nums1의 마지막 위치 // nums2의 모든 요소가 처리될 때까지 반복 while (p2 >= 0) { // nums1의 현재 요소가 더 크고, 아직 처리할 요소가 남아있다면 if (p1 >= 0 && nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } // nums2의 현재 요소가 더 크거나, nums1의 처리할 요소가 없다면 else { nums1[p] = nums2[p2]; p2--; } p--; } } 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...