코딩 테스트 대비! 파이썬으로 "유효한 팰린드롬(회문 - 뒤에서 부터 읽어도 똑같은 문자)" 문제 풀이

파이썬으로 "유효한 팰린드롬" 문제 풀이


문제 설명

영문 문자와 숫자로만 이루어진 문자열 s가 주어졌을 때, 대소문자를 구분하지 않고 알파벳과 숫자만 고려했을 때 s가 팰린드롬이면 True, 아니면 False를 출력하는 프로그램을 작성하세요.


제약 조건

- 1 <= s.length <= 2 * 105
- s는 영문 문자와 숫자로만 이루어져 있습니다.


예시 입출력

- s = "A man, a plan, a canal: Panama" → True
- s = "race a car" → False


솔루션 코드

def is_palindrome(s):
    # 문자열에서 알파벳과 숫자만 뽑아서 소문자로 변환
    filtered = [char.lower() for char in s if char.isalnum()]
    
    # 양쪽에서 포인터를 이용해 palindrome 확인
    left, right = 0, len(filtered) - 1
    while left < right:
        if filtered[left] != filtered[right]:
            return False
        left += 1
        right -= 1
        
    return True

# 테스트
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

코드 설명

1. 문자열 s에서 알파벳과 숫자만 뽑아내고 이를 모두 소문자로 변환하여 filtered 리스트에 저장합니다.
2. filtered의 맨 앞(left)과 맨 뒤(right) 인덱스를 가리키는 두 개의 포인터를 생성합니다.
3. left가 right보다 작은 동안 반복문을 실행합니다.
4. left와 right가 가리키는 문자가 다르면 False를 반환합니다.
5. left와 right를 각각 증가, 감소시킵니다.
6. 반복문이 종료되면 palindrome이므로 True를 반환합니다.

이 풀이의 시간 복잡도는 O(n)이며, 추가적인 공간을 filtered 리스트에 사용하므로 공간 복잡도는 O(n)입니다.

이 문제에서는 팰린드롬 확인을 위해 투 포인터 기법을 사용했습니다. 주어진 문자열에서 알파벳과 숫자만 추출하고 대소문자를 구분하지 않는 케이스 변환과정을 거쳤습니다. 이런 유형의 문자열 처리 및 팰린드롬 확인은 코딩 테스트에서 자주 출제되니 익숙해질 필요가 있습니다.