[TAVE/파이썬 알고리즘] Ch8 | 연결 리스트 - 13번 팰린드롬 연결 리스트(leetcode 234)

📌연결 리스트: 선형적인 자료구조이다. 구조체 각각이 서로 연결된 형태로 구성되어 있고 메모리 어딘가에 흩뿌려져 있다. 해당 구조체는 다음 구조체가 무엇인지에 대한 정보를 담고 있어 연결된 형태를 유지할 수 있는 것이다.

📌팰린드롬: 회문이라고도 부른다. 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말, 숫자, 문자열 등이다.

 

리스트 변환

1️⃣파이썬의 리스트로 변환한다.

q: List = []

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

2️⃣pop함수에 인덱스를 지정해 요소를 추출하며 같은 값인지 확인한다.

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

✅pop()

👉🏻리스트의 인덱스를 받아서 지운다.

✍🏻del과의 차이점: pop은 지워진 인덱스의 값을 반환한다.

 

📌전체코드

def isPalindrom(self, head: ListNode) -> bool:
    q: List = []

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

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

    return True

👉🏻문제점: 리스트는 동적 배열로 구성되어 있다. 때문에 맨 앞 아이템을 꺼내오면 모든 값이 한 칸씩 시프팅(Shifting)되기 때문에 시간 복잡도(O(n))가 발생한다.

 

데크를 이용한 최적화

✅데크(Deque)

👉🏻이중 연결 리스트 구조로 양쪽 방향 모두 추출할 수 있어 앞, 뒤 양쪽 방향에서 엘리먼트를 추가하거나 제거할 수 있다. 때문에 시간 복잡도 O(1)에 실행된다.

 

1️⃣데크 자료형을 선언한다.

#데크 자료형 선언
q: Deque = collections.deque()

node = head
while node in not None:
    q.append(node.val)
    node = node.next

 

2️⃣pop함수를 이용해 요소를 추출하며 같은 값인지 확인한다.

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

 

📌전체 코드

def isPalindrom(self, head: ListNode) -> bool:
    #데크 자료형 선언
    q: Deque = collections.deque()

    if not head:
        return True

    node = head
    while node in not None:
        q.append(node.val)
        node = node.next

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

 

고(Go)를 이용한 데크 구현

📌고는 데크 자료형을 지원하지 않기 때문에 일일히 직접 구현해야 한다. 

 

 

 

런너를 이용한 우아한 풀이

✅런너 기법

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

👉🏻연결리스트는 전체를 다 탐색해야 하므로 중간 위치나 길이를 파악하는 데에 배열에 비해 복잡하다. 때문에 대체로 fast runner와 slow runner를 나눈다. fast runner의 속도를 2배만큼 빠르게 설정하면 fast runner가 리스트 끝지점에 도착했을 때 slow runner는 정확히 리스트의 중간 지점에 도달하게 된다. 

 

1️⃣런너를 이용해 역순 연결 리스트 구성

👉🏻다른 방법과 다르게 연결 리스트 형태를 그대로 유지하며 풀이할 수 있다. 

👉🏻fast runner를 이용해 slow runner가 연결리스트 중간 지점에서 멈추게 하고, slow runner는 연결리스트를 탐색하면서 동시에 역순 연결리스트를 구성한다.

👉🏻연결리스트가 홀수의 원소를 갖는 경우, 가운데 원소를 배제하고 확인하도록 하기 위해 if문 사용한다.

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

 

2️⃣팰린드롬 여부 확인

👉🏻rev tail이 None이므로 그 전까지 while문을 돌린다. 이렇게 탈출하면 rev가 None인 동시에 팰린드롬이 증명이 되므로 True를 return한다.

👉🏻그 전에 탈출한다면 rev와 slow 각각의 연결리스트가 같지 않으므로 팰린드롬이 아닌 것이고 rev도 None이 아니기 때문에 False를 return할 수 있다.

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

📌전체 코드

def isPalindrom(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