[python] 정렬 - 투포인터 정리

📌 이번에 푼 문제

#	문제	출처	링크
1	Valid Palindrome	LeetCode	바로가기
2	Two Sum II - Input Array Is Sorted	LeetCode	바로가기
3	Squares of a Sorted Array	LeetCode	바로가기
4	Move Zeroes	LeetCode	바로가기
5	Maximum Average Subarray I	LeetCode	바로가기

💡 투포인터 종료조건 정리
종료조건은 웬만하면 while left < right.
단, Squares of a Sorted Array 처럼 left == right인 칸도 처리해야 하는 문제는 while left <= right로 둬야 한다.

• 맹점: "left == right을 처리해야 하나?" 가 기준
• 처리해야 하면 → <=
• 안 해도 되면 → <

---

1. Valid Palindrome

핵심

isalnum()으로 문자와 숫자만 True인 글자만 솎아내면서 양 끝에서 투포인터로 좁혀 들어간다. 문자/숫자가 아닌 칸은 비교하지 않고 포인터만 한 칸 옮긴다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():        # 문자·숫자 아니면 건너뛰기
                left += 1
            elif not s[right].isalnum():
                right -= 1
            elif s[left].lower() != s[right].lower():
                return False
            else:
                left += 1
                right -= 1
        return True

left == right인 가운데 한 글자는 자기 자신과 비교할 필요가 없으니 종료조건은 <로 충분하다.

---

2. Two Sum II - Input Array Is Sorted

어떻게 풀었나

이미 정렬되어 있으니, 두 수의 합이 target보다 작으면 left += 1, 크면 right -= 1 로 범위를 좁혔다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left + 1, right + 1]   # 문제는 1-indexed로 요구
            elif s < target:
                left += 1
            else:
                right -= 1

내가 몰랐던 점 / 배운 점

• 투포인터의 핵심은 "한 번 좁힌 건 되돌리지 않는다". left = 0으로 되돌리는 순간 투포인터가 아니다. 각 포인터는 한 방향으로만 움직여야 O(n)이 된다.

만약 numbers가 정렬(non-decreasing)되어 있지 않았다면?

① 해시맵 — O(n)

지나온 수를 {값: 인덱스}로 저장하면서, 각 수마다 target - 현재값이 맵에 있는지 확인한다.

def twoSum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

② 정렬 후 투포인터 — O(n log n)

값으로 정렬해야 하는데 원래 인덱스를 답으로 돌려줘야 하므로, 인덱스를 값 기준으로 줄 세운다.

def twoSum(nums, target):
    arr = sorted(range(len(nums)), key=lambda i: nums[i])  # 원래 인덱스를 값 기준 정렬
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[arr[left]] + nums[arr[right]]
        if s == target:
            return sorted([arr[left], arr[right]])
        elif s < target:
            left += 1
        else:
            right -= 1

💡 sorted(range(len(nums)), key=lambda i: nums[i]) 뜯어보기

• range(len(nums)) → 0, 1, 2, 3 ... 인덱스를 만든다
• key=lambda i: nums[i] → 그 인덱스를 nums[i] 값 기준으로 정렬한다
• 결과: 인덱스를 값 순서대로 줄 세운 리스트

---

3. Squares of a Sorted Array

그저 그런 풀이 — O(n log n)

제곱해서 sorted 하는 순간 정렬 비용 O(n log n)이 붙는다.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        new_arr = []
        for i in nums:
            new_arr.append(i ** 2)    # O(n)
        answer = sorted(new_arr)      # O(n log n)
        return answer

투포인터 풀이 — O(n)

이미 배열이 정렬되어 있으니, 제곱했을 때 가장 큰 값은 항상 양 끝 둘 중 하나다. 양 끝을 비교해 큰 쪽을 골라 결과의 뒤에서부터 채우면 된다.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = 0
        right = n - 1
        pos = n - 1               # 중요! 큰 값부터 뒤에 넣는다
        arr = [0] * n

        while left <= right:      # left == right 칸도 채워야 하므로 <=
            if nums[left] ** 2 < nums[right] ** 2:
                arr[pos] = nums[right] ** 2
                right -= 1
            else:
                arr[pos] = nums[left] ** 2
                left += 1
            pos -= 1
        return arr

💡 양 끝 절댓값(제곱값)을 비교해 가며 큰 쪽을 골라 뒤에서부터 채우는 수렴형 응용. 여기선 left == right인 마지막 한 칸도 채워야 하므로 종료조건이 <= 인 게 포인트.

---

4. Move Zeroes

내가 몰랐던 점 / 틀린 이유

• 새 배열을 만들어 append하거나 deque로 popleft 하는 건 in-place 규칙 위반이다. (원래 배열을 그대로 수정해야 함)

slow / fast + swap 풀이

fast는 계속 전진하고, 0이 아닌 값일 때만 swap 한다. slow는 0 자리에 멈춰서 대기하다가, 뒤에서 0이 아닌 값을 만나면 자리를 바꾼다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        -> 새 배열 / deque 만들어 쓰면 안 됨
        """
        slow = 0   # 다음 '0이 아닌 값'이 들어갈 자리
        fast = 0   # 배열을 처음부터 끝까지 훑는 탐색기

        while fast < len(nums):
            if nums[fast] == 0:
                fast += 1
            else:
                nums[fast], nums[slow] = nums[slow], nums[fast]
                slow += 1
                fast += 1

slow가 0 위치에서 멈춰 기다리기 때문에, 그 뒤에 나오는 0이 아닌 값과 자리를 바꿔 0을 자연스럽게 뒤로 밀어낸다.

---

5. Maximum Average Subarray I

그저 그런 풀이 — O(n * k)

윈도우를 한 칸씩 옮기며 매번 다시 sum 했다. 합을 구할 때마다 O(k)라 전체 O(n * k).

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        new_arr = []
        n = len(nums)
        for i in range(n - k + 1):
            a = nums[i:k + i]
            new_arr.append(sum(a))
        return max(new_arr) / k

좋은 풀이 — O(n)

첫 k개 합을 딱 한 번만 구하고, 그다음부터는 들어온 값 +, 빠진 값 − 로 차분만 갱신한다.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window = sum(nums[:k])      # 첫 k개 합을 한 번만 계산
        best = window
        for right in range(k, len(nums)):
            window += nums[right] - nums[right - k]   # 들어온 값 +, 빠진 값 -
            best = max(best, window)
        return best / k

"구간 합을 반복해서 구하는" 문제는 매번 다시 더하지 말고 경계를 옮기며 차분만 갱신하는 게 슬라이딩 윈도우의 정석이다.

---

✅ 마무리

키워드	내용	관련 문제
종료조건	left == right을 처리해야 하면 <=, 아니면 <	Squares of a Sorted Array
포인터 불가역성	한 번 좁힌 포인터는 되돌리지 않는다 (left = 0 복귀 금지) → O(n)	Two Sum II
isalnum()	문자·숫자만 걸러내며 양 끝에서 좁히기	Valid Palindrome
인덱스 값기준 정렬	sorted(range(n), key=lambda i: nums[i]) = 인덱스를 값 순서로 줄 세우기	Two Sum II (정렬 안 됐을 때)
수렴형 채우기	양 끝 절댓값 비교 후 큰 쪽을 결과 뒤에서부터 채움	Squares of a Sorted Array
slow / fast + swap	in-place 이동은 새 배열·deque 없이 두 포인터로 swap	Move Zeroes
슬라이딩 윈도우 차분	매번 다시 합산(O(n·k)) 말고 들어온 값 +, 빠진 값 − 로 갱신(O(n))	Maximum Average Subarray I