유효한 팰린드롬 Valid Palindrome

리트코드 125. Valid Palindrome

🤔 Q. 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

• 예제 1
  입력

  "A man, a plan, a canal: Panama"

  출력

  true

• 예제 2
  입력

  "race a car"

  출력

  false

'팰린드롬'이란
앞뒤가 똑같은 단어나 문장. 뒤집어도 같은 말이 되는 단어 또는 문장. 우리말로는 회문.

---

✏️ 풀이 1: 리스트로 변환

def isPalindrome(self, s: str) -> bool:
	# 전처리
	strs = []
    for char in s:
    	if char.isalnum():
        strs.append(char.lower())
        
    # 팰린드롬 여부 판별
    while len(strs) > 1:
    	if strs.pop(0) != strs.pop():
        	return False
            
    return True

• 입력값에서 제약 조건(영문자와 숫자)에 해당하는 문자만 따로 모은다.
• 맨 앞과 맨 뒤를 매칭해 나가면서 일치하지 않는 경우 False를 리턴한다.

---

✏️ 풀이 2: 데크 자료형을 이용한 최적화

def isPalindrome(self, s: str) -> bool:
	# 자료형 데크로 선언
    strs: Deque = collections.deque()
    
    # 전처리
    for char in s:
    	if char.isalnum():
        	strs.append(char.lower())
    
    # 필린드롬 여부 판별
    while len(strs) > 1:
    	if strs.popleft() != strs.pop():
        	return False
            
    return True

• 데크를 명시적으로 선언하면 좀 더 속도를 높일 수 있다.
• 리스트의 pop() 은 O(n) 이지만 데크의 popleft() 는 O(1) 이다.
• 참고자료 [Python] Deque.popleft()는 왜 빠른가?

---

✏️ 풀이 3: 슬라이싱 사용

def isPalindrome(self, s: str) -> bool:
	s = s.lower()
    # 정규식으로 불필요한 문자 필터링
    s = re.sub('[^a-z0-9]', '', s)
    
    return s == s[::-1] # 슬라이싱

• 파이썬은 문자열을 배열이나 리스트처럼 자유롭게 슬라이싱할 수 있다.
• 코드가 줄어들고, 내부적으로 C로 빠르게 구현되어 훨씬 더 좋은 속도를 기대할 수 있다.

문자열 슬라이싱
문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리.
S[:] : 사본. 참조가 아닌 값 복사.
S[::-1] : 뒤집는다.

---

✏️ 풀이 4: C 구현

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;
}

• 위치 포인터를 직접 조작하기 때문에 매우 빠르게 실행된다.
• C와 같은 컴파일 언어는 파이썬 같은 인터프리터 언어에 비해 더욱 좋은 성능을 낸다.

---

📌 정리

• char.isalnum() : 영문자, 숫자 여부 판별 함수
• char.lower() : 소문자 변환 함수
• list.pop(i) : 리스트에서 인덱스 위치를 가져오는 함수
• deque.popleft() : 데크에서 가장 왼쪽의 것을 가져오는 함수
• S[:] : 문자열 값 복사
• S[::-1] : 문자열 뒤집기