“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/palindrome-linked-list/
여름에 한국에 다녀온 이후로 백지 상태가 되었다가 처음부터 다시 시작했다. 이제서야 연결 리스트 챕터에 들어왔다.
연결 리스트(링크드 리스트)는 학부 때 자료구조 시간 초반에 배웠던 것 같다. 그때도 여전히 이쪽과는 거리가 먼 문과생 타입이었기 때문에 C로 자료구조를 만들고 노드 탐색, 추가, 삭제 기능을 만드는 데 너무 힘들었었다. 물론 한 학기가 다 되도록 이해조차 가지 않아서 죽을 쒔었지. 교재를 몇 번이고 읽어도 익숙하지 않은 개념들 뿐이라 내가 왜 이 길에 들어왔는가 고통을 느꼈던 기억이 자꾸 떠오른다.
나는 이과 애들이랑 뇌 구조가 다른 건지 이런 자료구조들이 한참만에 조금씩 조금씩 이해하기 시작했다. 알고리즘 수업을 들을 때 정도엔 잘 쓰진 못해도 거부감은 덜했지. 그렇게 조금씩 발전해 가는 것이 수포자의 기쁨이었는데 졸업하고 잘못된 곳에 취업하면서 배웠던 거의 모든 것들이 깡그리 쓸모 없는 것으로 변해버려서 길이 상처로 남아 있다. 왜 용기 있게 다른 일할 곳을 찾지 않았는가.(비빌 곳 하나 없는 취약한 상태였으니까요.)
아무튼 오늘도 잡설이 길어졌다. 이번 문제는 각 노드가 0-9로 구성된 연결 리스트가 팰린드롬인지 아닌지 판별하는 것이다. 뭘 해야하는 지는 알겠는데 리트코드 페이지가 아닌 로컬에서 이 문제를 풀려면 파이썬 리스트 []로 주어진 인자를 NodeList라는 임의의 연결 리스트 자료형 클래스로 만들어야 했다.
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
예를 들어 입력값 [1,2,2,1]을 ListNode로 만드는 것 부터가 우선이었다. 오랜만에 쓰는 재귀함수라 조악해도 이해하자.
param = [1,2,2,1]
def createListNode(index: int) -> ListNode:
if index + 1 >= len(param):
return ListNode(param[index])
else:
return ListNode(param[index], createListNode(index + 1)]
first = createListNode(0)1. 파이썬 리스트로 바꾸기
연결 리스트를 파이썬 리스트로 바꾸면 첫문제로 풀었던 Valid Palindrome에서처럼 쉽게 풀 수 있을 것이다. 다른 언어에서라면 어떻게 될지 의문이다.
def isPalindrome(head: Optional[ListNode]) -> bool:
node = head
lst = []
while node:
lst.append(node.val)
node = node.next
while len(lst) > 1:
if lst.pop(0) != lst.pop():
return False
return True
리스트의 pop(0)과 pop()을 비교하는 것만으로 충분하다. 파이썬의 편리함. 하지만 예전 문제에서처럼 pop(0)는 O(1)이 아닌 O(n)의 복잡도를 가지므로 Deque를 사용하면 더 나아질 것이다. (deque는 이중 연결 리스트 구조이므로 노드의 앞뒤를 모두 참조로 가진다.)
2. deque를 이용하기
deque를 쓰는 것 말고는 1과 같다.
def isPalindrome(head: Optional[ListNode]) -> bool:
dq = collections.deque()
node = head
while node:
lst.append(node.val)
node = node.next
while len(lst) > 1:
if lst.popleft() != lst.pop():
return False
return True
3. Runner 기법을 이용하기
책을 읽고는 이 방법의 기발함에 놀랐다. 세상엔 정말 똑똑한 사람이 많다. 러너 기법이라는 건, 리스트를 순회할 때 2개의 포인터를 동시에 사용하는데, 예를들어 포인터 하나는 (fast) 한 번에 두 칸을 이동하고 나머지 하나는 (slow) 한 칸을 이동한다. 그러면 fast가 끝에 도달할 때 slow는 리스트의 중간지점에 도달하게 되므로 slow가 거기서부터 값을 비교하거나 뒤집기를 하는 등 여러가지로 활용할 수 있다고 한다.
def isPalindrome(head: Optional[ListNode]) -> bool:
rev: ListNode = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
if fast: # 리스트 길이가 홀수인 경우 slow를 한 칸 더 전진시켜서 중간을 가리키도록 맞춘다.
slow = slow.next
while rev and rev.val == slow.val:
rev, slow = rev.next, slow.next
return not rev참 간결하고 효율적이다. 책에서 투포인터 개념이 등장할 때부터 그랬지만 포인터 두 개를 동시에 움직인다는 생각이 나로서는 기발하다. 더군다나 fast가 두 칸, slow가 한 칸씩 움직이면 fast가 끝날 때에 slow가 중간에 가 있다는 당연한(!) 것조차 재미있다.
여기서는 slow가 중간에 갈 때까지 rev라는 역순 연결 리스트를 만든다.(전체가 [1,2,2,1]라면 rev는 [2,1]이 됨) 그리고 중간부터 slow와 비교하면 팰린드롬인지 아닌지 알 수 있겠지. 대단하다.