ch6-1(leetcode 125). 유효한 팰린드롬

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

- leetcode 125번 ( https://leetcode.com/problems/valid-palindrome/ )

 

풀이방법 1. 

문제에서는 팰린드롬은 영문자와 숫자만을 대상으로 한다고 했으므로, 조건에 맞는 문자들만 리스트에 넣는다. 

이후 리스트의 맨 앞과 맨 뒤의 원소를 각각 제거한 다음, 두 원소의 값이 같은지를 비교한다. 

값이 하나라도 다르면 앞뒤가 똑같지 않은 것이므로 False를, 전부 같으면 True를 리턴한다. 

 

파이썬에서 기본으로 제공되는 isalnum() 메소드를 사용하면 특정 문자가 alphanumeric(영문자와 숫자)인지 아닌지를 간단하게 구분할 수 있다. 

파이썬에서 제공하는 기본 메소드들은 내부적으로 속도가 훨씬 빠른 C언어를 통해 구현되어 있다. 따라서 직접 파이썬의 for loop로도 코드를 만들 수 있겠지만 기본 메소드를 사용하는 것이 더 속도가 빠르다. 

 

풀이방법 2. 

더 효과적인 데크(deque) 자료형을 사용한다. 

데크와 리스트의 차이점은 맨 앞의 원소를 제거하는 popleft(), pop(0) 메소드에 걸리는 시간이다. 

데크는 투 포인터라서 pop()와 popleft()이 모두 O(1)인 반면, 리스트는 pop()에는 O(1)이 소요되지만 pop(0)에는 리스트 전체 중 0번째 인덱스를 직접 찾는 셈이 되므로 O(n)이 소요된다. 

 

데크 자료형은 외부 라이브러리가 아닌 collections 라이브러리를 사용하며, 간단하게 선언할 수 있다.

deque = collections.deque()

 

collections 라이브러리에는 deque 외에도 편리한 기능이 갖춰진 기본 자료구조를 갖고 있기 때문에 공식문서를 참고해서 알아두면 좋겠다. 

https://docs.python.org/3/library/collections.html

 

풀이방법 3. 

정규식으로 조건에 맞는 문자들만 필터링한 다음, 문자열 슬라이싱으로 비교하는 방법도 있다. 

특히 문자열의 경우 슬라이싱(slicing)을 사용할 수 있는지 고려해보자. 생각보다 다양한 슬라이싱 방법들이 많다. 

 

정규식으로 문자열을 필터링하고 싶은 경우 re 라이브러리를 사용한다. 

https://docs.python.org/3/library/re.html

 

re.sub(정규식 패턴, 대체할 문자열, 원본 문자열)

re 라이브러리의 sub 메소드는 원본 문자열 중 패턴에 일치하는 문자열을 대체할 문자열로 바꾸는 역할을 한다. 

result = re.sub(r"[a-zA-Z]", "eee", "abc123def")
print(result)	# 'eee123eee'

 

문자열 슬라이싱

가장 기본적인 방법으로는 문자열의 특정 왼쪽 인덱스부터 특정 오른쪽 인덱스까지를 가져올 수 있다. 

string[left: right] 은 string 변수의 left 번째 인덱스부터 (right-1)번쨰 인덱스까지를 가져온다. 

string = "little red riding hood"
print(string[7:10])	# red

 

또는 인덱스에 음수를 사용하면 오른쪽 인덱스부터 왼쪽 인덱스까지, 역수 방향으로 문자열을 가져올 수 있다. 

text = "olleh"
print(text[-2:-4])	# el

 

문자열 전체를 뒤집거나, n칸씩 뛰어넘어서 문자열을 가져오는 것도 가능하다. 

text = "hello"
print(text[::-1])	# olleh

 

또는 문자열 슬라이싱으로 기존 문자열을 복사할 수도 있다. 이는 기존의 문자열의 값을 가져오고 싶으나 참조하게 되는 문제로 원본 값을 가져오지 못할 때, 참조가 아니라 값을 복사하기 위해서 사용할 수 있다. 

text = "text"
print(text[:])	# text

 

 

참고한 포스트

https://ponyozzang.tistory.com/335