https://leetcode.com/problems/valid-palindrome/

Python에 비해 고성능을 낼 수 있는 C로 풀이해본다.
코드는 <자바 알고리즘 인터뷰>에서 가져왔다.

1️⃣ C

참고로 'bias'는 인덱스 오프셋 (Index Offset), 즉 배열이나 메모리 주소 계산에서 기준점으로부터의 차이를 나타낸다.

// Runtime 0ms
bool isPalindrome(char *s) {
	int bias_left = 0;
    int bias_right = 1;
    
    int str_len = strlen(s);
    for (int i = 0; i < str_len; i++) {
    	// 스킵 포인터 처리
        while (!isalnum(s[i + bias_left])) }
        	bias_left++;
            if (i + bias_left == str_len)
            	return true;
        }
        while (!isalnum(s[str_len - i -bias_right])) {
        	bias_right++;
        }
        
        if (i + bias_left >= str_len - i - bias_right)
        	break;
            
        // 팰린드롬 비교
    	if (tolower(s[i+ bias_left]) != tolower(s[str_len - i - bias_right]))
        	return false;
    }
	return true;
}

• bias_left와 bias_right를 통해 숫자나 알파벳이 아닌 글자를 건너 뛰는 작업을 하면서 팰린드롬 비교도 같이 이뤄진다.
• 가독성이 비교적 좋진 않지만 속도 최적화를 우선시한 코드이다.

2️⃣ Python

1. 포인터

class Solution:
    def isPalindrome(self, s: str) -> bool:
        processed = []

        for c in s:
            if c.isalnum():
                processed.append(c.lower())
         
        left = 0
        right = len(processed)-1

        while left < right :
            if processed[left] != processed[right]:
                return False
            left+=1
            right-=1

        return True

• 두 개의 포인터 사용

2. 데크 자료형

def isPalindrome(self, s:str) -> bool:
	# 자료형 데크로 선언
    strs: Deque = collections.deque()
    
    for char in s:
    	if char.isalnum():
        	strs.append(char.lower()) # Deque 자료형에 append()
            
    while len(strs) > 1:
    	if strs.popleft() != strs.pop():
        	return False
            
    return True

• 데크 자료형을 이용
  cf) Python의 collections.deque는 이중 연결 리스트(doubly linked list)와 유사하게 구현되어 있으며, 정확히는 💫block 기반의 이중 연결 리스트이다.

• 데크가 아닌 리스트를 사용하면 pop(0)은 O(n)인데 반해, 💫데크의 popleft()는 O(1)이다. 각각 n번씩 반복하면 리스트 구현은 O(n^2), 데크 구현은 O(n)으로 성능 차이가 크다.

• Python의 리스트는 💫동적 배열(dynamic array)로 구현되어 있다. 그러므로 💫pop()또는 pop(-1)은 O(1)이고 앞이나 중간에서 꺼내는 pop(0), pop(1) 등은 O(n)이다.

3. filter()

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = ''.join(filter(str.isalnum, s)).lower()
        return cleaned == cleaned[::-1]

filter()는 “조건을 만족하는 요소만 남기는” 함수다.

형식: filter(조건함수, 반복가능한 거)
조건함수 → True/False 반환
filter() → 조건함수에서 True 나온 요소들만 골라냄
결과는 iterator (list가 아님 → 필요한 경우 list()로 감싸야 함. 위 코드에서는 문자열 반환해야하므로 ''.join()에 매개변수로 넣었음.)

근데 filter()보다 더 Pythonic한 건 아래처럼 리스트 컴프리헨션으로 처리하는 것

cleaned = ''.join(c.lower() for c in s if c.isalnum())

e.g. filter()로 문자열에서 알파벳/숫자만 추출 후 리스트화

s = "A man, a plan"
filtered = filter(str.isalnum, s)
print(list(filtered))
# ['A','m','a','n','a','p','l','a','n']

학습/복습한 것

• reversed()는 list가 아닌 iterator를 반환한다
• 리스트 reversed()를 쓰는것보다 그냥 슬라이싱을 쓰는 게 더 빠르게 동작한다. 문자열 슬라이싱 연산은 내부적으로 C로 구현되어 최적화가 되어있기 때문에 매우 빠르게 동작한다.
  그래도 시간 복잡도로 따지면 여전히 O(k) (복사 비용)이다.
  진짜 O(1) 뷰가 필요하면 memoryview나 NumPy를 사용한다.

# NumPy의 O(1) 슬라이싱 (뷰)
import numpy as np
arr = np.array([1, 2, 3, 4, 5])
view = arr[1:4]  # O(1) - 복사 없음, 뷰만 생성

• lower() upper()
• list명.pop(index번호) : index번호안쓰면 맨 오른쪽 거 꺼냄.