LeetCode - The World's Leading Online Programming Learning Platform

Array를 활용한 풀이

문제 풀이 아이디어

주어진 링크드리스트가 Palindrome인지 확인하기 위해서는 링크드리스트를 거꾸로 탐색할 수 있어야 한다. 하지만 링크드리스트는 거꾸로 탐색할 수 없다. 거꾸로 탐색하기 위해서 Array로 링크드리스트를 바꾸어서 풀면 쉽게 풀 수 있다.

코드

// Array를 이용한 풀이
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        var array = [Int]()
        var next = head
        
        // 링크드리스트를 정방향으로 탐색하면서 Array로 옮긴다.
        while let n = next {
            array.append(n.val)
            next = n.next
        }
        
        // Palindrome인지 확인
        for i in 0..<(array.count / 2) {
            if array[i] != array[array.count - i - 1] {
                return false
            }
        }
        
        return true
    }
}

Runner를 활용한 풀이

문제 풀이 아이디어

숨은 조건

위 문제는 아주 간단하게 풀 수 있지만 공간 복잡도가 O(N)이다. 문제에 주어진 조건 중에서 “Follow up: Could you do it in O(n) time and O(1) space?”가 있다. 공간복잡도를 O(1)을 사용하기 위해서는 주어진 링크드리스트를 다른 자료구조로 바꾸어서는 안된다.

Runner 알고리즘

Runner는 링크드리스트의 역탐색, 혹은 링크드리스트의 중간을 찾아야 하는 경우에 유용하게 사용할 수 있는 알고리즘이다. Runner는 fase와 slow라는 2개의 말 그대로 “Runner”를 출발시키는데 fast는 2개의 노드씩, slow를 1개의 노드씩 이동 시킨다. 이렇게 하면 fast가 링크드리스트의 끝에 도달할 때 slow는 링크드리스트의 중앙에 도달할 수 있게 된다.

Palindrome인지 확인하기 위해서는 중앙을 기준으로 두 개의 링크드 리스트로 잘랐을 때 왼쪽에는 역방향 탐색, 오른쪽에는 정방향 탐색을 하며 노드들을 비교해야 한다.

따라서 Runner를 아래 2가지 단계를 통해서 활용한다.

1. fast가 끝까지 도달할 때까지 slow를 활용해서 역방향 링크드리스트(이하 reversed)를 만든다.
2. fast가 끝까지 도달하면 (= slow가 링크드리스트의 중앙에 도달하면) slow (오른쪽 부분 정방향 탐색)와 reverse (왼쪽 부분 역방향 탐색)을 통해서 Palindrome인지 확인한다.

아래 그림으로 설명해보겠다.

Runner 1단계

첫 번째 단계는 slow를 절반까지 이동시키면서 reverse를 만드는 과정이다.

출발 이전에는 reverse는 아직 빈 리스트이며 fast와 slow 모두 head에 위치 해있다.

이제 Runner들을 1번 이동 시키자. fast는 2칸 slow는 1칸이다. 여기서 reverse를 만들기 위해서 slow를 이동 시키기 전에 slow가 위치한 부분을 reverse의 head로 지정해야 한다.

다음 이동이다. 여기서 reverse를 같은 원리도 만든다. slow를 이동시키기 전에 slow가 위치했던 부분을 reverse의 head로 지정해야 한다. 이 때 기존의 head를 next로 이동해야 한다는 점을 명심하자

위 2번의 이동을 통해서 fast가 끝까지 이동했다. 링크드리스트의 길이가 위 예시처럼 홀수인 경우에는 fast.next가 nil일 때, 짝수인 경우는 fast가 nil일 때 끝까지 이동한 것이 된다. 따라서 while문을 사용해서 fast ≠ nil && fast.next ≠ nil 조건을 사용하면 fast를 끝까지 이동시킬 수 있다.

여기서 주의할 점은 링크드리스트의 길이가 위처럼 홀수인 경우에는 reverse와 slow를 비교하기 전에 slow를 1칸 더 이동해야 한다는 것이다. 왜냐하면 정중앙에 위치한 “3”은 Palindrome 여부를 판단하는데 쓰이면 안되기 때문이다. 따라서 fast ≠ nil인 경우에 (= 길이가 홀수) slow를 한칸 더 이동 시키자.

Runner 2단계

2단계는 이제 간단하다. slow와 reverse를 끝까지 이동시키면서 각각의 노드의 val이 동일한지 보면 확인하면 된다. slow는 오른쪽 절반을 정방향으로 탐색한다. reverse는 왼쪽 절반을 역방향으로 탐색한다. 이동할 때마다 노드의 val이 일치하면 palindrome, 아니면 palindrome이 아니다.

코드

나머지 설명은 코드에 자세하게 적었다.

// Runner 기법을 활용한 풀이
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        // reverse: 현재 링크드리스트를 거꾸로 뒤집은 링크드리스트의 head
        var reverse: ListNode? = nil
        // slow는 1칸씩 이동하는 포인터, fast는 2칸씩 이동하는 포인터
        var slow = head, fast = head
        
        // fast가 끝까지 이동할 때까지
        while fast != nil && fast?.next != nil {
            // fast는 2칸 이동
            fast = fast?.next?.next
            // 거꾸로 리스트의 다음 head의 next = 거꾸로 리스트의 현재 head
            let nextOfReverse = reverse
            reverse = slow // 거꾸로 리스트의 현재 head를 slow로 교체 (역으로 1칸 감)
            reverse?.next = nextOfReverse // head가 한칸 이동했으므로 과거의 head가 현재 head의 next가 됨
            slow = slow?.next // slow 1칸 이동
        }
        
        // fast가 nil이 아닌 경우 = 링크드리스트의 node 수가 홀수인 경우
            // 이렇게 되면 현재 slow의 위치는 링크드리스트의 정중앙
            // 근데 정중앙 값은 plaindrome을 판별하는데 영향을 끼치면 안되므로 slow 1칸 이동
        if fast != nil {
            slow = slow?.next
        }
        
        // slow의 현재 위치: 정중앙 바로 다음 위치
        // reverse의 현재 위치: 정중앙 바로 이전 위치
        // slow의 진행방향: 정방향
        // reverse의 진행방향: 역방향
        // 따라서 slow와 reverse를 진행하면서 비교해나간다.
        while reverse != nil, reverse?.val == slow?.val {
            slow = slow?.next
            reverse = reverse?.next
        }
        
        // palindrome이라서 reverse가 끝까지 이동했으면 true, 중간에 while문 끊겼다면 false
        return reverse == nil
    }
}