반응형
팰린드롬이란?
- 앞뒤가 똑같은 단어나 문장
- ‘기러기’, ‘오디오’
- ‘소주 만 병만 주소’
대소문자를 구분하지 않음
- Level
- Anna
영문자와 숫자만을 대상으로 함
- “A man, a plan, a canal: Panama” → 영문자만 추리면 아래와 같음
- 팰린드롬 맞음
문제에 대한 예시
풀이 1. 리스트로 변환
def is_palindrome_1(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
문제풀이에 필요한 개념
String
- isalnum() 메소드
- Return True if the string is an alpha-numeric string, False otherwise.
char1 = 'a' print(char1.isalnum()) # True char2 = '5' print(char2.isalnum()) # True char3 = '$' print(char3.isalnum()) # False - lower() 메소드
- 대문자를 소문자로 변환해서 반환
str1 = 'ABC' print(str1.lower()) # abc str2 = 'AbC' print(str2.lower()) # abc
List
- pop() 메소드
lists = ['a', 'b', 'c', 'd'] print(lists.pop()) # d print(lists) # ['a', 'b', c'] print(lists.pop(0)) # 리스트에서 0번째 인덱스(가장 앞)에 해당하는 'a' 반환 print(lists) # ['b', 'c'] - Remove and return item at index (default last).
풀이 2. 데크 자료형을 이용한 최적화
def is_palindrome(s:str)->bool:
import collections
strs = 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- list가 아닌 deque를 이용
if strs.pop(0) != strs.pop(): # strs가 list
if strs.popleft() != strs.pop(): # strs가 deque- list의 pop(0)의 시간 복잡도는 O() O(n)
- [0, 1, 2, 3, 4] pop(0) , [None, 1, 2, 3, 4] → [1, 2, 3, 4]
- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- 맨 앞의 element에 pop()을 적용하면 뒤의 요소들을 한칸씩 왼쪽으로 모두 옮겨야 함
- 반면 deque의 popleft() 시간 복잡도는 O(1)
- 내부적으로 doubly linked list으로 삽입/삭제에 효율이 좋음
- 1→ 2→ 3→4→5→6, 2만 pop하면 1→3→4→5→6 (뒤는 유지)
풀이 3. 슬라이싱 사용
def is_palindrome_3(s:str) -> bool:
import re
s = s.lower()
s = re.sub('[^a-z0-9]', '', s) # 숫자 문자가 아닌 문자열을 공백으로 변환
return s==s[::-1]
문제 풀이에 필요한 개념
- 정규식
- [] : 문자 클래스로 [] 사이의 문자들과 매치
- [a-z] : 소문자 알파벳과 매치
- [a-zA-Z] : 알파벳 모두
- [0-9] : 숫자 모두
- [^a-z] : 소문자 알파벳을 제외한 문자와 매치
- [^a-z0-9] : 소문자 알파벳과 숫자를 제외한 문자와 매치
re.sub(first, second, third)
- first : 정규식
- second : first에 매치되는 요소를 second로 치환
- third : 적용될 문자열
str = 'abcABC123!@#'
import re
# 소문자를 공백으로 치환
str_except_small_letter = re.sub('[a-z]', '', str)
print(str_except_small_letter) # ABC123!@#
# 대문자를 공백으로 치환
str_except_big_letter = re.sub('[A-Z]', '', str)
print(str_except_big_letter) # abc123!@#
# 숫자를 공백으로 치환
str_except_numbers = re.sub('[0-9]', '', str)
print(str_except_numbers) # abcABC!@#
# 숫자,문자를 공백으로 치환
str_except_special = re.sub('[a-zA-Z0-9]','', str)
print(str_except_special) # !@#
Reference
1) 책 "파이썬 알고리즘 인터뷰"
2) stackoverflow: deque.popleft() and list.pop(0). Is there performance difference?
반응형
'코딩테스트' 카테고리의 다른 글
| Leetcode 387. First Unique Character in a String (0) | 2024.11.03 |
|---|
