[파이썬 알고리즘] 팰린드롬 연결리스트

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:

        head_list = []
        now = head
        while True:
            head_list.append(now.val)
            if now.next != None: 
                now = now.next
                continue
            break

        if head_list == head_list[::-1]:
            return True
        else:
            return False

연결리스트를 배열로 변환한 후, 팰린드롬 확인 작업을 거쳤다.

      #  if head_list == head_list[::-1]:
      #      return True
      #  else:
      #      return False

       while len(head_list) > 1:
               if head_list.pop(0) != head_list.pop()
                return False
       return True

if문을 배열을 뒤집는 방식으로 비교하지 않고, 배열에서 pop() 함수를 사용하여 비교할 수도 있다.

 

---

 

하지만, head_list.pop(0)을 사용하면, 첫 번째 아이템을 추출할 때 속도 문제가 생긴다. 맨 앞 아이템을 가져오기 적절한 이중 연결 리스트 구조로, 시간 복잡도 O(1)으로 양방향으로 추출할 수 있는 데크를 사용하면 더욱 효율적이다.

import collections

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        head_list = collections.deque()
        if not head:
            return True
        node = head
        while node is not None:
            head_list.append(node.val)
            node = node.next

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

데크(deque)를 선언하는 부분과, pop() 부분만 다르고 나머지 코드는 동일하다.

 

---

 

이번엔 배열이나 데크를 사용하지 않고, 연결리스트 그대로 풀이하는 방법이다.

2개의 포인터를 동시에 사용하여 연결 리스트를 순회하는 런너 기법을 사용한다. 한 포인터를 다른 하나의 포인터보다 앞서게 해 병합 지점, 중간 위치 등을 판별할 때 유용하다.

다음과 같이 두 배 차이나는 빠른 런너, 느린 런너를 각각 두고 포인터를 이동시킨다. 빠른 런너가 연결 리스트의 끝에 도달하면 느린 런너는 연결 리스트의 중간 지점에 위치하게 된다. 그 중간 지점에서부터 값을 비교하거나 뒤집는 등 여러 가지 방법으로 활용할 수 있다.

1->2->3->2->1 인 연결 리스트에 런너를 적용하는 풀이를 그림으로 나타낸 것이다.

 

 

전체 코드

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPalindrome(self, head: Optional[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

slow = fast = head

빠른 런너 fast와 느린 런너 slow는 head를 초깃값으로 지정하고 시작한다.

 

 

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

fast의 next가 존재하지 않을 때까지 fast를 두 칸씩 이동한다.

여기서 중요한 것은 역순 연결 리스트를 생성하는 rev와 느린 런너 slow를 이동시키는 코드 부분인데, 꼭 다중 할당으로 처리해야 한다.

 

 

rev, rev.next = slow, rev
slow = slow.next

만일, 위처럼 두 번에 나누어 rev와 slow로 설정한다면 실행되지 않을까?

rev = 1, slow = 2->3 (slow는 연결 리스트, slow.next=3이라는 의미)이라고 가정했을 때

한 줄로 한꺼번에 다중 할당한 rev, rev.next, slow = slow, rev, slow.next의 경우는

rev = 2->3, rev.next = 1, slow = 3이 되고, 최종적으로 rev = 2->1, slow = 3이 된다.

작업이 동시에 일어나기 때문에 모든 작업이 중간 과정 없이 한 번의 트랜잭션으로 끝난다.

 

 

그렇지만 똑같이 rev = 1, slow = 2->3 라고 가정하고

rev, rev.next = slow, rev  
slow = slow.next

처럼 나눠서 실행한다면,

rev = 2->3, rev.next = 1 따라서 rev = 2->1이 된다.

여기서 rev=slow였기 때문에 slow도 함께 2->1이 된다. 따라서 slow = slow.next는 우리가 원하는 3이 아닌 1이 되어 slow = 1이 된다.

그러므로 반드시 한 줄의 다중 할당이 필요하다.

 

 

if fast:
    slow = slow.next

연결 리스트가 홀수일 때와 짝수일 때는 처리를 다르게 해 주어야 한다. 1->2->3->2->1의 경우와 같이 홀수일 경우에는 slow 런너가 중앙값인 3에서 끝나는데, 3은 팰린드롬 체크에서 제외해야 하기 때문이다. 따라서 fast가 마지막 값에서 끝나는 홀수일 경우, slow를 한 칸 더 이동한다.

 

 

다음으로는 팰린드롬 여부를 확인한다.

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

return not rev

rev가 존재하고, rev의 값과 slow의 값이 같다면 slow와 rev를 한 칸씩 이동하여 끝날 때까지 비교한다.

만일, rev.val과 slow.val이 다르다면 팰린드롬이 아니므로 while문을 빠져나와 바로 not rev(rev가 끝까지 이동하지 않았으므로 값이 존재하므로 rev는 True)를 반환한다.

팰린드롬이 맞다면 slow와 rev 모두 끝까지 이동해 둘 다 None이 된다. None은 False로 분류되므로, True가 반환된다.

 

return not rev 대신 return not slow라고 써도 결과는 같다.

연결 리스트를 다른 자료형으로 변환하지 않고 바로 풀이한 런너 방식 풀이였다.

역순 연결 리스트를 만드는 rev 부분에서 많이 헷갈렸는데, 이 문제를 통해 다중 할당의 동작 방식을 제대로 이해하고 간다.

한 줄로 다중 할당하는 방식을 사용해야만 문제를 제대로 풀이할 수 있다는 것을 꼭 염두해 두자.