LeetCode[ 125 | Python ] Valid Palindrome
업데이트:
문제
주어진 문자열에서 숫자와 알파벳이 아닌 모든 문자를 무시하고 소문자로 변환했을 때, 주어진 문자열이 팰린드롬인지 검증하는 문자열 문제.
풀이
시도
- 띄어쓰기를 제거한다.
- 문자열을 순회하며 숫자, 알파벳인지 검증한 후 유효한 문자라면
res리스트에 따로 저장한다. res를 절반만큼 순회하며 팰린드롬인지 확인한다.- 앞과 뒤 문자열이 일치하지 않으면 즉시 False를 반환한다.
- 성공적으로 순회가 끝나면 True를 반환한다.
통과는 할 수 있었지만
필요 이상의 리스트가 사용되고,
띄어쓰기와 특수문자가 따로 처리되어 반복문을 한번 더 사용해야한다는 점이 아쉬웠다.
끝과 처음을 비교한다는 점에서 스택과 포인터를 사용하면 충분히 해결할 수 있을 거란 생각이들기도 했지만, 그보다 간단하다고 생각되는 투포인터를 이용해 개선해보기로 했다.
class Solution(object):
def isPalindrome(self, s):
s = list(s.replace(' ', '').lower())
res = []
for i in range(len(s)):
if s[i].isalnum():
res.append(s[i])
for i in range(len(res) // 2):
if res[i] != res[-i-1]:
return False
return True
개선
l,r두 포인터를 초기화한다.- 양 쪽 모두 중간 지점으로 이동하며 두 포인터가 가리키는 지점의 문자가 일치하는지 확인한다.
- 이 때 문자가 숫자나 알파벳이 아니라면 포인터를 추가적으로 이동한다.
- 일치하지 않는다면 즉시 False를 반환한다.
- 두 포인터가 정상적으로 중간지점에서 만난다면 True를 반환한다.
결과적으로
실행시간을 48ms -> 28ms,
메모리를 17.7MB -> 14.7MB 로 줄일 수 있었다.
class Solution(object):
def isPalindrome(self, s):
s = list(s.lower())
l, r = 0, len(s) - 1
while l < r:
while not s[l].isalnum() and l < len(s)-1:
l += 1
while not s[r].isalnum() and r >= 0:
r -= 1
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
생각 & 정리
개선한 코드도 아쉬운 점은 남아있었다.
투 포인터를 수행하기 전에 전체 문자를 소문자로 만들어 이미 O(n)이 소요된다는 점이었다.
따라서 개선된 코드 또한 최악의 경우 O(2n) 정도가 된다고 판단되었고,
이를 개선하는 방법에는 처음부터 어떤 문자가 들어있을지 모르는 문자열을 모두 소문자로 변환하는 것이 아니라, 개선한 코드에서 이미 특수문자가 아닌 코드들은 필터링 되고 있기 때문에 두 문자를 비교하는 부분만 소문자로 바꿔주어도 되겠다고 판단했다.
if s[l] != s[r]:
return False
# --> s = list(s.lower()) 삭제
if lower(s[l]) != lower(s[r]):
return False
결과적으로 실행시간은 눈에 띄게 줄지 않았으나 메모리 사용률이 감소했다 !
(14.7MB -> 13.9MB)
리트코드를 처음 접해보면서 내가 짠 코드가 상위 몇 퍼센트인지 확인할 수 있었고 덕분에 내 코드에 대한 기준점이 생긴 것 같아 좀 통쾌했다.
반면 작은 부분들이라 생각되었던 부분들이 한 서버안에서 모여 꽤나 큰 메모리 낭비를 초래할 수 도 있다는 생각이 들기도했다.
댓글남기기