[ Python ] leetcode 문제로 연결리스트 개념 정리하기 1

 

 

 

---

 

 

 

포스팅 목적

leetcode 문제를 다뤄보면서 연결리스트에 대한 개념을 정리합니다.

파이썬 알고리즘 인터뷰라는 서적을 참고하여 작성하였습니다.

 

 

이번 포스팅에서 다루는 leetcode 문제

Palindrome Linked List - LeetCode

• 234. Palindrome Linked List ( 팰린드롬 여부를 확인하는 문제 )

 

팰린드롬이란?

순서를 뒤집어도 똑같은 문자열을 의미합니다.
( ex. [1, 2, 1] [1, 2, 2, 1] ['A', 'B', 'A'] )

 

 

 

풀이방법 1 : 리스트 반환

• 팰린드롬 여부를 판단하기 위해서는 앞뒤로 추출 할 수 있는 자료구조가 필요합니다.
• 파이썬의 리스트는 pop()에 인덱스를 지정하여 원하는 인덱스의 값을 추출할 수 있습니다.
• 따라서 연결리스트를 파이썬 리스트로 변환하여 pop()을 이용하면 해결할 수 있습니다.

def isPalidrome(self, head) -> bool:
  q = []

  if not head:
    return True

  node = head
  
  # 리스트 변환
  while node is not None:
    q.append(node.val)

  # 팰린드롬 판별
  while len(q) > 1:
    if q.pop(0) != q.pop():
      return False
    
  return True

• head가 비어있다면 True를 반환합니다 ( 조건에 있음 )
• node변수가 head를 가리키게 한 뒤 head가 None, 즉 값이 없을때까지 리스트 q에 append 합니다.
• 모든값이 리스트 q에 append 되었다면 q에서 pop()을 사용하여 값을 추출하여 비교합니다
• pop은 단순히 값을 가져오는것이 아닌 뽑아서 사용하고 원본에서 삭제합니다.
  즉 원본 리스트 q에서 값이 두개씩 사라집니다.
• 팰린드롬 판별쪽 코드와 같이 인덱스를 지정하여 양쪽의 수가 동일한지 판별하는 것이 핵심입니다.
• 당연하게도 pop()을 사용하기위해 파이썬 리스트로의 변환이 필요합니다.

 

 

풀이방법 2 : 데크를 이용한 최적화

• 리스트를 활용한 방법보다 좀 더 최적화를 할 수 있는 방법입니다.
• 리스트 변환 풀이방법의 문제점은 첫번째 아이템을 추출할때의 속도가 문제입니다.
• 동적배열로 구성된 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아닙니다.
• 첫 값을 꺼내오게되면 모든값이 한칸씩 시프팅되며 시간복잡도O(n)이 발생하기 때문입니다.
• 따라서 맨 앞 데이터를 가져올 때 O(n)이내에 처리할 수 있는 자료형이 필요한데,
  데크가 O(1)에  양쪽방향 모두 추출할 수 있습니다.

# 데크를 이용환 최적화
import collections

def isPalidrome2(self, head) -> bool:
  q = collections.deque()

  if not head:
    return True
  
  node = head
  while node is None:
    q.append(node.val)
    node = node.next

  while len(q) > 1:
    if q.popleft() != q.pop():
      return False
  return True

• 성능은 약 2배이상 빨라진 최적화 방법이었습니다 .

 

 

 

풀이방법 3 : 러너를 이용하기

• 책에서 소개하는 제대로된 풀이방법인 Runner 기법을 활용한 방법입니다.

# 러너를 이용한 방법
def isPalidrome3(self, head) -> bool:
  rev = 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.next

  # 팰린드롬 여부 확인
  while rev and rev.val == slow.val:
    slow, rev = slow.next, rev.next
  return not rev

• 빠른러너와 느린 러너를 출발점인 head에서 동시에 출발시킵니다
• 빠른러너는 두 칸 느린러너는 한 칸씩 이동하며,
  빠른러너가 끝에 다다르면 느린러너는 중간지점에 도착하게됩니다.
• 이동하면서 역순으로 연결리스트 rev를 생성하는 로직을 slow앞에 덧붙입니다.
• 첫 rev값은 None에서 시작하고, 러너가 이동하면서..
  1->None, 2->1->None ... 와 같이 이전값으로 연결되는 구조가 됩니다.
• 이렇게 만들어진 역순 연결리스트 rev를 반복합니다.
• slow의 나머지 이동경로와 역순으로 만든 rev노드를 하나씩 비교하면서 팰린드롬인지 확인합니다.
• 정상적으로 비교가 종료됐다면 slow와 rev가 모두 끝까지 이동해 둘다 None이 될 것입니다.
• 최종 코드는 return not rev , return not slow 모두 가능합니다.
• 연결리스트를 다른 자료형으로 바꾸지 않고 데크를 사용했을때와 비슷한 성능을 내는 방법입니다.