[파이썬(python) 알고리즘] 런너(Runner)기법

런너(Runner) 기법

연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법.

한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.

 

연결리스트의 경우 중간 위치나 길이를 파악하는 데에 배열에 비해 상대적으로 복잡하다. (전체를 다 탐색해야 하므로 O(n)의 시간이 소요됨)

따라서 fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다.

중간위치를 찾아냄으로써 값 비교 (palindrome linked list 문제), 뒤집기를 시도하는 등의 연결 리스트 문제에서 여러 방식으로 활용이 가능하다.

 

Ex. Palindrome Linked List (리트코드 234번)

: 입력값으로 주어진 연결리스트가 palindrome인지 판별하라

 

- runner를 이용한 풀이

    1) 연결리스트형태를 그대로 유지하며 풀이 가능.

    2) palindrome을 앞서는 투포인터를 이용해서 풀 수 있었다.

 

그러나 연결리스트의 경우에는 그 길이를 파악하는데에만 O(n)의 시간이 걸리므로, 연결리스트의 중간을 탐색 중 파악하기가 어렵다. (길이를 파악해서 하려면 길이를 알아내는 데에만 O(n)의 시간이 걸리고, 또 이중연결리스트가 아니라면 역순으로 이동하기는 어렵기 때문.)

 

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

fast runner가 연결리스트 순회를 마치면 중간지점까지 역순의 연결리스트가 만들어지고, 나머지 반과 해당 역순연결리스트를 비교해서 palindrome 여부 check

→ 약간 투포인터와 비슷한 포인트 (반으로 쪼개서 양방향에서 접근하겠다)

 

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        rev = None # reversed linked list
        slow = fast = head # 두 개의 runner (init은 처음 값으로)
        # runner를 이용하여 역순 연결 리스트 구성
        
        while fast and fast.next: # fast running (slow runner가 딱 연결 리스트 중간까지 도달하도록 함)
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        
        if fast: # 연결리스트가 홀수의 원소를 갖는 경우, 가운데 원소를 palindrome 체크에서 배제하도록 함.
            slow = slow.next
        
        # palindrome 여부 체크
        while rev and slow.val == rev.val:
            rev, slow = rev.next, slow.next
        
        return not rev 
    # palindrome이 아니어서 while loop을 탈출했다면 rev가 None이 아니므로 False일 것이고, 정상적으로 while이 종료되었다면 rev가 None이므로 True일 것이다. (slow로 해도 상관 X)