알파벳, 숫자, 그리고 다양한 기호가 섞여 있는 문자열이 있다고 가정해 봅시다. 이 문자열에는 대문자와 소문자가 함께 포함되어 있을 수 있습니다. 이때 소문자와 숫자만을 기준으로(대문자는 소문자로 변환) 해당 문자열이 회문(palindrome)인지 판별하는 것이 목표입니다. 쉼표, 공백, 콜론 같은 기호는 모두 무시합니다.
문제 이해하기
예를 들어 문자열이 "A Man, a Plan, a Canal: Panama"라고 한다면, 위의 규칙을 적용하면 "amanaplanacanalpanama"가 됩니다. 이 문자열은 앞에서 읽어도 뒤에서 읽어도 같으므로 회문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 빈 문자열
x = ""를 정의합니다. - 입력 문자열의 각 문자
c를 하나씩 읽습니다.c가 소문자 또는 숫자라면 그대로x에 추가합니다.c가 대문자라면 소문자로 변환한 뒤x에 추가합니다.
- 정리된 문자열
x가 회문이라면True를, 아니라면False를 반환합니다.
구현 예제
아래 코드를 통해 실제 구현 방법을 살펴보겠습니다.
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
x = ""
diff = ord('a') - ord('A')
for i in s:
if ord(i)>=ord('a') and ord(i)<=ord('z') or ord(i)>=ord("0") and ord(i)<=ord("9"):
x+=i
elif ord(i)>=ord('A') and ord(i)<=ord('Z'):
i = chr(diff+ord(i))
x+=i
return x == x[::-1]
ob1 = Solution()
print(ob1.isPalindrome("A Man, a Plan, a Canal: Panama"))코드 설명
ord()함수는 문자의 아스키(ASCII) 코드 값을 반환하며,chr()함수는 아스키 코드 값을 다시 문자로 변환합니다.diff = ord('a') - ord('A')는 대소문자 간의 아스키 코드 차이(32)를 미리 계산해 둔 값입니다. 이를 활용하면 대문자를 손쉽게 소문자로 변환할 수 있습니다.x[::-1]은 파이썬의 슬라이싱 문법으로, 문자열을 거꾸로 뒤집은 결과를 얻습니다. 원본 문자열과 뒤집은 문자열이 같다면 그 문자열은 회문입니다.
실행 결과
입력
s = "A Man, a Plan, a Canal: Panama"
출력
true
시간 복잡도
이 알고리즘은 문자열을 한 번 순회하여 정리한 뒤(O(n)), 회문 여부를 확인하기 위해 한 번 더 비교합니다(O(n)). 따라서 전체 시간 복잡도는 O(n)이며, 추가로 정리된 문자열을 저장하기 위한 O(n)의 공간이 필요합니다.