🤔 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]: 문자열 뒤집기
미친 존재 우주 먼지