[LeetCode] #141 Linked List Cycle - Swift 풀이

노션에서 보기

0141 Linked List Cycle

문제

(자세한 워딩은 생략)

요약하자면 Singly Linked로 구성된 List에서 tail이 list 어디론가 다시 연결되는 cycle이 발견되는 경우 true를, 순환 없이 끝나면 false를 리턴하라는 문제이다.

 

그리고 이제부터 답을 향한 대 서사시를 시작해보도록 하겠다😩

 

는.. 그 전에

풀이

혹시나 답만 필요한 구글러가 있을 지 모르므로 답 코드 먼저 공개하며 시작.

 

func hasCycle(_ head: ListNode?) -> Bool {

    if head == nil { return false }

    var slow = head
    var fast = head?.next

    while true {
        if fast == nil { return false }
        if slow === fast { return true }
        slow = slow?.next
        fast = fast?.next?.next
    }

}

알고 보면 너무나도 간단하다.

다른 속도로 움직이는 두 노드를 설정하고 그 노드가 같은 경우가 생기는 지를 비교하면 된다. 더 빨리 움직인 노드가 nil이라면 사이클이 없는 것이므로 false,

같은 경우가 생긴다면 사이클이 있는 것이므로 true를 리턴하면 끝.

 

하지만 그 '알고 보면'까지 가는 게 정말 오래 걸렸다😢

지난한 과정들

먼저, 노드의 클래스는 아래와 같이 정의되어 있다.

/** 
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

1. 중복 val 검사

처음에는 도저히 어떻게 할지 모르겠어서 약간의 희망(?)을 가지고

중복된 val이 등장하면 사이클이 있는 거라는 설계로 코딩을 해보았다.

(마침 예시에는 중복된 val이 없음)

 

func hasCycle(_ head: ListNode?) -> Bool {
    var st = Set<Int>()
    var arr = [Int]()
    var temp = head

    while temp != nil && st.count == arr.count {
        st.insert(temp!.val)
        arr.append(temp!.val)
        temp = temp?.next
    }

    return temp != nil ? true : false
}

지나온 val을 담는 Set과 Array를 하나씩 만들고, 두개의 수가 달라지면 사이클이 있다고 간주하는 것이다.

하지만 당연히 어림도 없었다.

(사실 어림도 없는 거 치곤 2개 빼고 다 통과,,)

2. extension 활용

그렇다면 previous 노드를 가리키는 포인터를 추가해주면 어떨까 생각이 들었다.

 

prev가 nil이 아니라면 이미 그 전에 prev 추가가 된 것이므로 사이클이 발생했다는 증거일 것이다.

func hasCycle(_ head: ListNode?) -> Bool {
    var current = head
    var next = head?.next

    while true {
        if next == nil { return false }
        if next?.prev != nil { return true }
        next?.prev = current
        current = next
        next = next?.next
    }
}

여기서 정말 멍청이 같았던 건 우선 저 코드를 쓴 다음에 extension 추가 시도를 한 것이다.

그렇다. extension으로는 저장 프로퍼티 추가가 되지 않는다.

extension ListNode {
    public var prev: ListNode? = nil //❌ Extensions must not contain stored properties
}

3. Collection 활용

그 다음으로 시도한 방법은 1에서 val의 중복 검사를 한 것처럼 이번엔 node 자체의 중복 검사를 하는 것이었다.

 

3-1 Set에 담기

1에서 한 것과 똑같이 Set과 Array의 개수를 비교해보려고 했다.

하지만 애석하게도 Swift의 Set엔 Hashable 프로토콜을 따르는 타입만 담을 수 있었다. ListNode로는 불가능

 

3-2 Array의 .contains 활용하기

Array에는 담을 수 있어서, .contains를 활용하여 중복 체크를 해보려고 했다.

 

func hasCycle(_ head: ListNode?) -> Bool {
    if head == nil { return false }

    var arr = [ListNode]()
    var temp = head

    while true {
        if temp == nil { return false }
        arr.append(temp!)
        temp = temp?.next
        if arr.contains(temp!) { return true }
    }
}

하지만 .contains를 쓰려면 Array에 담긴 타입이 Equatable 프로토콜을 따르고 있어야 했다.

그래서 extension으로 추가를 해주었다.

extension ListNode: Equatable {
    public static func ==(l: ListNode, r: ListNode) -> Bool {
        return l.next == r.next && l.val == r.val
    }
}

 

솔직히 이번엔 진짜 되겠다 싶었는데...

❌ process exited with signal SIGSEGV ❌

 

....

 

빠르게 구글링을 해보니 허용되지 않은 메모리에 접근했다는 세그먼트 오류였다.

정말 이 한 문제 풀자고 별 오류를 다 보는 구나..!

4. 참조 비교

이쯤 되니 정말 너무 답답해서 결국 LeetCode solution을 보고 말았다.

 

1번으로 나온 해답은 Set을 활용하는 거였다. 자바랑 파이썬 예시였는데 이 두 언어에서는 Set에 ListNode를 담는 게 가능한가보다.

 

그리고 2번으로 나온 게 Floyd's Cycle Finding Algorithm이었다.

바로 위에서 구현한 두 노드의 탐색 속도를 다르게 하여 비교하는 방식이다.

 

그런데 사실 이 방식도 방식인데 내가 진짜 아차차 했던 것 다른 포인트였다.

바로 제목과 같은 참조 비교.

func hasCycle(_ head: ListNode?) -> Bool {

    if head == nil { return false }

    var slow = head
    var fast = head?.next

    while true {
        if fast == nil { return false } //🥲🥲🥲🥲🥲🥲🥲
        if slow === fast { return true }
        slow = slow?.next
        fast = fast?.next?.next
    }

}

 

이미 글로도 한판 정리했는데, ===로 class 인스턴스를 비교할 수 있다는 사실을 까맣게 잊고 있었다.

(사실 헷갈리고 있었다. 극 초반에 참조 비교가 ~=인줄알고 시도했다가 안된다고 생각해서 바로 접었다.)

 

하..만약 참조끼리 비교가 가능하다는 개념이 박혀 있었다면 뻘짓을 덜 했거나 다른 풀이를 생각해 냈을 것 같다.

 

---

 

마치며

너무나도 멍청한 이 지난한 과정을 글로 남기는 이유는

어찌됐든 이 문제를 풀며 제대로 잡혀 있지 않던 Swift 문법 부분들을 한번씩 공부할 수 있었기 때문에

아주아주 뜻깊은 시간이었다는 생각이 들어서다!

 

오늘 헤맨 부분들은 절대 잊지 않으리..