알고리즘 문제풀이 정리 - Two Pointers (1)

9/9/2025·임성혁

수정일: 9/10/2025

neetcode.io에서 Two Pointers 관련 문제를 풀고 정리한 게시글이다.

Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).

Example 1:

Input: s = "Was it a car or a cat I saw?"
 
Output: true

Explanation: After considering only alphanumerical characters we have "wasitacaroracatisaw", which is a palindrome.

Example 2:

Input: s = "tab a cat"
 
Output: false

Explanation: "tabacat" is not a palindrome.

Constraints:

1 <= s.length <= 1000
s is made up of only printable ASCII characters.

양쪽 끝에서 알파벳 혹은 숫자가 나올 때 서로 같은지 비교하고 두 포인터가 서로 만날 때까지 검증하는 식으로 접근했다.

trial1

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i=0
        j=len(s)-1
        while i<j:
            a=s[i].lower()
            b=s[j].lower()
            print(a+b)
            if not ('a' <= a <= 'z') or ('0' <= a <= '9'):
                i+=1
                continue
            if not ('a' <= b <= 'z') or ('0' <= b <= '9'):
                j-=1
                continue
            if a==b:
                print(23456)
                i+=1
                j-=1
            else:
                return False
        print(12345)
        return True

case "0P"인 경우 틀렸다고 나왔다.

무엇이 문제인가 싶어 위의 코드대로 print하도록하고 디버킹을 해보았다.

처음에는 str 길이가 2개이면 로직에 허점이 있나 싶었지만,

이것만으로는 알 수가 없어서 숫자를 중간에 하나 더 넣어 "01P"로 디버깅 해보았다.

str 길이가 2인건 전혀 상관이 없음을 알 수 있다.

0P 에서 1P로 넘어가는 것을 보아 하니 a에 대한 검증이 if 문에서 true로 나와 i+=1 후 continue 되었다는 것을 알 수 있었다.

처음에는 s[i]이 숫자이면 a의 type이 int가 되어 문제가 발생하나 싶어 type도 출력해봤는데 str가 맞았다.

알고보니 or를 썼기에 not을 붙이기전에 소괄호를 하나 더 써서 랩핑했어야하는 것.. 사소한 실수였지만 놓치니 발견하는게 생각보다 어려웠다.

trial2

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i=0
        j=len(s)-1
        while i<j:
            a=s[i].lower()
            b=s[j].lower()
            if not (('a' <= a <= 'z') or ('0' <= a <= '9')):
                i+=1
                continue
            if not (('a' <= b <= 'z') or ('0' <= b <= '9')):
                j-=1
                continue
            if a==b:
                i+=1
                j-=1
            else:
                return False
        return True

수정해서 통과한 정답.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ''
        for c in s:
            if c.isalnum():
                newStr += c.lower()
        return newStr == newStr[::-1]

isalnum() 함수는 문자열이 알파벳(한글 포함)이나 숫자로만 이루어졌는지 확인하는 함수이다. 공백, 특수문자를 제외하는 상황에서 쓰인다.

오로지 알파벳 혹은 숫자로만 이루어져있어야 true를 반환하고 아닌경우에는 false를 반환한다.

여기서는 공백/특수문자 인경우 newStr에 포함시키지 않기 위해 사용되었다.

문자열 s를 순회하며 공백 및 특수 문자를 제거한 문자열(정확히는 알파벳 혹은 숫자으로만 이루어진) newStr을 만들고 이를 뒤집은 문자열과 직접 비교해 참 거짓을 반환하도록 하였다.

코드가 짧고 직관적이지만, 메모리 사용량 부분에서 개선의 여지가 있다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
 
        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1
            while r > l and not self.alphaNum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = l + 1, r - 1
        return True
    
    def alphaNum(self, c):
        return (ord('A') <= ord(c) <= ord('Z') or 
                ord('a') <= ord(c) <= ord('z') or 
                ord('0') <= ord(c) <= ord('9'))

이 접근법은 문자열 양끝을 포인터로 삼아서 서로 중앙으로 향하며 검증을 이어가는 투포인터 방식이다.

디테일에서 조금 차이가 있지만 기본적으로 내가 쓴 풀이와 같다.

Given an array of integers numbers that is sorted in non-decreasing order.

Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.

There will always be exactly one valid solution.

Your solution must use O(1)O(1) additional space.

Example 1:

Input: numbers = [1,2,3,4], target = 3
 
Output: [1,2]

Explanation: The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, index2 = 2. We return [1, 2].

Constraints:

2 <= numbers.length <= 1000
-1000 <= numbers[i] <= 1000
-1000 <= target <= 1000

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        nums=len(numbers)
        i=0
        j=nums-1
        while i<j:
            temp=numbers[i]+numbers[j]
            if temp==target:
                return [i+1,j+1]
            elif temp<target:
                i+=1
            else:
                j-=1
        return [0,0]

이미 배열이 오름차순으로 정렬된 형태로 주어지니 배열의 양끝을 각각 포인터로 잡고 target과 비교하면서 범위를 좁혀나가면 된다.

투포인터의 합이 target 보다 작을 경우 왼쪽 포인터를 증가시키고, 클 경우에는 오른쪽 포인터를 감소시키면 된다.

문제에는 해답이 단 하나만 존재한다고 했으므로 이를 반복하면 해당 해답에 이를 수 있다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []

배열에서 나올 수 있는 모든 조합들에 대해 target과 같은지 일일히 검증하는 방법이다. 당연히 투포인터보다 비효율적이다.

최악의 경우 n(n-1)/2 회 순회하여야함으로 시간복잡도 $O(n^2)$ , 공간복잡도는 $O(1)$ 이다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            l, r = i + 1, len(numbers) - 1
            tmp = target - numbers[i]
            while l <= r:
                mid = l + (r - l)//2
                if numbers[mid] == tmp:
                    return [i + 1, mid + 1]
                elif numbers[mid] < tmp:
                    l = mid + 1
                else:
                    r = mid - 1
        return []

이진 탐색으로 접근하는 방법이다.

index 0 부터 순차적으로 증가 시키며 target 그 자체가 아니라 target - numbers[i]를 찾아야할 값으로 여긴다.

그러면 정렬된 나머지 배열에서 해당 숫자와 일치하는 요소를 빠르게 찾기 위해 이진탐색을 수행하는 것이다.

n개 요소에 대해 각각 log n 에 해당하는 이진 탐색을 수행하므로 시간 복잡도는 $O(n \log n)$ 이다.

공간복잡도는 $O(1)$ .

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        mp = defaultdict(int)
        for i in range(len(numbers)):
            tmp = target - numbers[i]
            if mp[tmp]:
                return [mp[tmp], i + 1]
            mp[numbers[i]] = i + 1
        return []

해시테이블을 이용한 접근법이다.

이진 탐색처럼 target-numbers[i]를 찾아야할 값으로 본다. 해당 값이 dictionary에 있는지 확인하고, 있으면 두 값을 반환한다.

없으면 (index i의 값, 1-indexed)를 (key, value)로 dictionary에 등록한다.

이러한 흐름은 이진탐색과 유사하면서도 다르다. 해시테이블은 이미 등록되어있는 경우에 대해서 빠르게 찾을 수 있기에, 앞에서부터 하나씩 dictionary에 등록하면서 과거의 등록된 값과 일치하는게 있는지 살펴보는 것이다. 반면 이진탐색은 i보다 앞의 숫자들에 대해서는 이미 검증을 마쳤으므로, 아직 살펴보지 않은 뒤의 숫자들에 대해 탐색을 진행한다.

이진탐색보다 빠르지만, dictionary에 저장해야하기에 메모리를 더 많이 요구한다.

시간 복잡도는 $O(n)$ , 공간 복잡도는 $O(n)$ 이다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
 
        while l < r:
            curSum = numbers[l] + numbers[r]
 
            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
        return []

투포인터 접근법이다. 나의 풀이와 같은 흐름. 시간 복잡도는 $O(n)$ , 공간 복잡도는 $O(1)$ 이다.

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
 
Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2:

Input: nums = [0,1,1]
 
Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
 
Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 1000
-10^5 <= nums[i] <= 10^5

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort();
        for i in range(len(nums)):
            j,k = i+1, len(nums)-1
            target = nums[i]
            while j<k:
                tmp = nums[j] + nums[k]
                if tmp + target == 0:
                    ans.append([nums[i],nums[j],nums[k]])
                    break;
                elif tmp + target < 0:
                    j+=1
                else:
                    k-=1
 
        return ans

nums[i] + nums[j] + nums[k] == 0 인 모든 경우를 찾으라는 것은, 다르게 말하면 nums[j] + nums[k] = - nums[i] 인 경우를 찾으라는 것과 같다.

i에 대해 for문을 순회하면 반복문 안에서 - nums[i]는 상수가 되고, 이는 - nums[i]을 만족하는 twoSum을 찾은 것과 같은 꼴이다.

그래서 각 i에 대해 투포인터로 twoSum을 수행하고, 일치하는 경우가 있으면 ans 배열에 집어넣는 식으로 구현했다.

그렇게 testcase를 통과하는줄 알았으나,

이렇게 모든 숫자가 0인 경우 [0,0,0]이 중복해서 들어간다는 문제가 있었다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort();
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:
                continue
            j,k = i+1, len(nums)-1
            target = nums[i]
            while j<k:
                tmp = nums[j] + nums[k]
                if tmp + target == 0:
                    ans.append([nums[i],nums[j],nums[k]])
                    break
                elif tmp + target < 0:
                    j+=1
                else:
                    k-=1
 
        return ans

[0,0,0]이 중복해서 들어가는 문제를 피하기 위해 반복문에서 확인하는 숫자가 직전의 숫자와 같다면 건너뛰도록하는 if문을 추가했다.

이제 문제를 해결했다 생각하며 testcase를 돌려보았는데 다른 case에서 문제가 발생했다.

-1(i)이 같은 경우가 있으면서 j, k가 다를 수 있는 경우를 고려하지 못한 것이다.

사실 중요한 본질은 -i를 만족하는 j+k가 한쌍 이상 있을 수 있다는 점이다. 단지 해당 testcase에서 우연히 -1이 2번 출연했기에 trial1에서 걸리지 않았을 뿐이다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort();
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:
                continue
            j,k = i+1, len(nums)-1
            target = nums[i]
            while j<k:
                tmp = nums[j] + nums[k]
                if tmp + target == 0:
                    ans.append([nums[i],nums[j],nums[k]])
                    j+=1
                    k-=1
                elif tmp + target < 0:
                    j+=1
                else:
                    k-=1
 
        return ans

조건을 충족하는 i, j, k를 찾아도 break하지 않고 이어서 끝까지 찾도록 코드를 수정했다.

하지만 또 다른 예외를 만나게 되었으니, 바로 j와 k가 모두 중복해서 등장하는 경우이다.. j와 k에 대한 중복이 있을 경우도 고려해주어야한다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set()
        nums.sort();
        for i in range(len(nums)):
            j,k = i+1, len(nums)-1
            target = nums[i]
            while j<k:
                tmp = nums[j] + nums[k]
                if tmp + target == 0:
                    ans.add((nums[i],nums[j],nums[k]))
                    j+=1
                    k-=1
                elif tmp + target < 0:
                    j+=1
                else:
                    k-=1
 
        return [list(t) for t in ans]

예외처리 잘하면 해결할 수 있을 것 같았으나 너무나 많은 예외에 지쳐 결국 set으로 중복을 제거해 해결했다.

시간 복잡도는 $O(n^2)$ 이다.

정말 edge case가 끝없이 쏟아졌다.. 앞으로는 기본 제공되는 test case에 대해서만 돌려보지 않고 스스로 edge case를 고민해보고 test case에 포함시켜야겠다. 문제에 안일하게 접근했을 때 겪을 수 있는 모든 오류를 순차적으로 겪은 느낌이다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = set()
        nums.sort()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        tmp = [nums[i], nums[j], nums[k]]
                        res.add(tuple(tmp))
        return [list(i) for i in res]

모든 경우의 수에 대해 모두 고려하는 방법이다. 가장 비효율적이다.

시간 복잡도: $O(n^3)$ , 공간 복잡도: $O(m)$

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        count = defaultdict(int)
        for num in nums:
            count[num] += 1
 
        res = []
        for i in range(len(nums)):
            count[nums[i]] -= 1
            if i and nums[i] == nums[i - 1]:
                continue
 
            for j in range(i + 1, len(nums)):
                count[nums[j]] -= 1
                if j - 1 > i and nums[j] == nums[j - 1]:
                    continue
                target = -(nums[i] + nums[j])
                if count[target] > 0:
                    res.append([nums[i], nums[j], target])
 
            for j in range(i + 1, len(nums)):
                count[nums[j]] += 1
        return res

해당 풀이는 hash map을 사용해 중복을 피하면서 조건에 맞는 i, j, k를 찾는다.

먼저 모든 수에 대해 몇번 등장하는지 숫자를 센다.

그리고 for문을 돌면서 i 이상인 j들을 for문으로 탐색한다. 만약 target(-nums[i] -nums[j]) 이 하나 이상 존재한다면 triplet이 존재하는 것이므로 res(정답 배열)에 추가한다.

2개의 if문으로 edge case도 잘 다루었음을 확인할 수 있다.

(중복제거를 위해 i,j의 숫자가 같을 때, 그리고 현재 j가 직전 j와 같을 때 건너뜀)

횟수를 셀 때 index를 추가하는게 아니라 숫자를 추가하기만 하면 되는 점을 잘 활용한 것 같다.

시간 복잡도: $O(n^2)$ , 공간 복잡도: $O(n)$

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        # 1. 정렬(Sort)
        nums.sort()
 
        # 2. for문을 수행하며 첫번째 숫자 고정
        for i, a in enumerate(nums):
            if a > 0:
                break
						
            # 3. 중복 제거
            if i > 0 and a == nums[i - 1]:
                continue
 
            # 4. 투 포인터로 나머지 두 숫자 찾기
            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                # 5. 합에 따른 포인터 이동
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    # 6. 중복제거 (두번째 숫자)
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
 
        return res

정렬(Sort)

투 포인터를 사용하기 위해 배열을 오름차순으로 정렬
for문을 수행하며 첫번째 숫자 고정

a, 즉 nums[i]가 0보다 클 때 break하는 이유 :

배열이 정렬되어 있으므로, 첫번째 숫자가 양수이면 나머지 두 숫자도 양수가 되어 합이 0이 될 수 없음.
중복 제거

같은 값의 첫번 째 숫자가 반복되는 것을 방지하여 중복된 결과를 제거.
투 포인터로 나머지 두 숫자 찾기
합에 따른 포인터 이동
중복 제거 (두 번째 숫자)

시간 복잡도: $O(n^2)$ , 공간 복잡도: $O(1)$ 또는 $O(n)$ (정렬 알고리즘에 따라 다름), $O(m)$ (출력 list)

이렇게 Two Pointers 관련 3문제를 풀어보았다.

다음 글에서 남은 2문제를 풀고 Two Pointers를 마무리할 예정이다.

알고리즘 문제풀이 정리 - Two Pointers (1)

알고리즘 문제풀이 정리 - Arrays & Hashing (4)