팰린드롬 연결 리스트(Palindrome Linked List - 234 from Leet Code)

Reference: Palindrome Linked List

🎯 문제 의의

• 문제 자체의 난이도는 높지 않았습니다. 연결 리스트로 구현된 자료를 반환하며 리스트에 담아 처리하면 기존의 팰린드롬 문제와 다를게 없기 때문이고, 또한 이러한 풀이가 다른 방식의 풀이와 속도 측면에서 큰 차이가 나지 않기 때문에 이 방법으로도 충분한 풀이입니다. 아래는 제 풀이입니다.

  ''' 문제 조건
  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  '''
  
  # 나의 풀이
  class Solution:
      def isPalindrome(self, head: ListNode) -> bool:
          head_list = []
          while head:
              head_list.append(head.val)
              head = head.next
          return head_list == head_list[::-1]

  
  

  node를 순회하며 값을 head_list에 담아 처리하고, head_list의 palindrome 여부를 판단합니다. 위의 return문의 Boolean은 요소를 하나하나 탐색하며 팰린드롬 여부를 파악하는 것보다 더 빠른 효율을 보여줍니다. 기능적으로는 큰 차이가 없지만 이 문제를 통해 새로운 방식인 런너 기법을 알게 되었습니다.

💻 런너 기법

• 런너(Runner)는 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용합니다. 두 포인터의 위치를 다르게 하여 한 포인터가 다른 포인터보다 앞서게 되면 병합 지점이나, 중간 위치, 길이 등을 판별하는 기준으로 사용할 수 있습니다.
• 2개의 포인터는 빠른 런너(Fast Runner), 느린 런너(Slow Runner)라고 부르는데, 일반적으로 빠른 런너는 두 칸씩 건너뛰고, 느린 런너는 한 칸씩 이동하게 됩니다. 이렇게 되면, 빠른 런너가 끝에 도달했을 경우 느린 런너는 중앙에 도착하게 됩니다. 이 상황을 이용해 문제를 해결할 수 있습니다.
• 성능은 위의 풀이와 비슷하지만 연결 리스트를 다른 자료형으로 변환하거나 편법을 사용하지 않고 그 자리에서 바로 풀이함으로써 좀 더 연결 리스트답게 풀 수 있습니다.

📈 런너를 이용한 문제 풀이

• 런너를 이용해 연결리스트의 Palindrome 문제를 풀이하면 아래와 같습니다.

  def isPalindrome(self, head: ListNode) -> 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

  코드를 해석해보겠습니다.

• 변수 설명

  rev = None -> 느린 런너를 역순으로 담을 연결리스트입니다. 느린 런너의 끝이 None이어야 하므로 rev의 초기값을 None으로 초기화해줍니다.
  slow -> 한번에 한칸씩 움직이는 느린 런너입니다. 시작은 head 노드로 합니다.
  fast -> 한번에 두칸씩 움직이는 빠른 런너입니다. 느린 런너와 동시점인 head 노드에서 시작합니다.

• 런너 이동 경로

  즉, 두칸씩 움직이는 빠른 런너가 마지막에 도착했을 때, 느린 런너는 연결리스트의 정중앙에 위치하고, rev는 slow가 움직인 기록이 거꾸로 기록되어 있습니다. 이를 예시로 표현하면

  1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1

  에서 빠른 런너(fast)가 1 -> 3 -> 5 -> 3 -> 1의 경로로 이동했을 때, 느린 런너(slow)는 1 -> 2 -> 3 -> 4 -> 5로 이동한 상태이며, rev는 4 -> 3 -> 2 -> 1 -> None 이 연결된 연결리스트가 됩니다. 즉, 여기서 느린 런너가 한칸씩 앞으로 가며 rev와 비교해서 모든 요소가 같다면 이는 Palindrome을 이룬다고 할 수 있습니다.

• 역순 연결 리스트 구성(rev)

  while fast and fast.next: # fast.next가 없다면 fast.next.next에서 에러가 발생하므로 둘다 체크해야합니다.(개수가 짝수인지 홀수인지 모르기 때문)
      fast = fast.next.next # 두 칸씩 이동
      rev, rev.next, slow = slow, rev, slow.next 

  slow = slow.next는 slow가 한 칸씩 이동한다는 것입니다.

  rev, rev.next = slow, rev는 slow가 1 -> 2로 이동할 때, rev는 2 -> 1이 됩니다. 정확히 말하면 rev라는 것은 slow의 현재보다 한칸 이전 상태이며, rev.next에는 현재 slow의 노드를 할당합니다.

• if fast:
      slow = slow.next

  fast가 남아있다는 뜻은 위의 반복문에서 마지막에 fast는 존재하지만 fast.next는 존재하지 않아서 탈출한다는 뜻이고, fast가 두칸 씩 움직일 때 해당상황이 발생하기 위해서는 홀수개의 런너가 존재해야합니다. 그래서 가운데 값에 slow가 멈추는 상황을 방지하기 위해 한 칸 더 움직입니다. 위의 예시를 기준으로 생각해보면, rev는 4에 있는 상황이지만 slow는 가운데 값인 5에 멈춰있습니다. 그래서 한 칸 더 앞으로 움직여 4의 노드로 움직여주는 작업이 필요한 것입니다.

• 팰린드롬을 판별합니다.

  while rev and rev.val == slow.val:
          slow, rev = slow.next, rev.next

📌 Learning Point

• 단순히 문제를 풀고 넘어가는 것보다 중요한 것은 문제에서 배울 수 있는 점을 찾는 것이고, 해당 문제의 난이도는 쉬웠지만 이 문제를 통해 런너의 개념을 학습하게 되었습니다. 연결리스트의 경우 이러한 속도차의 개념으로 문제를 해결할 수 있고, 여기에 추가적으로 생각해본 문제는 다음과 같습니다.
  1. 연결리스트가 아닌 다른 자료구조에서 사용 가능한 개념인가?
     • 일반적인 투포인터 풀이 등 리스트 같은 자료형에서 index의 움직임을 다르게하여 문제를 해결할 수 있을 것 같습니다. 물론 다른 자료형의 경우 하나 하나 자료를 탐색할 경우가 아니라면 더 많은 옵션이 있기 때문에 불필요할 것 같긴 하지만 가능한 풀이라고 생각됩니다.
  2. 속도 차이가 2배가 아닌 문제상황이 있을 수 있는가?
     • 팰린드롬은 가운데를 기준으로 양쪽이 데칼코마니 같은 형태이므로 속도차이가 2배로 진행되었지만 문제 상황에 따라 다른 속도도 가능하다고 생각됩니다.