LeetCode - 142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/?envType=study-plan&id=level-1 

Linked List Cycle II - LeetCode

 

내 첫번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # return the node where the cycle begins. If there is no cycle, return null
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # [0] 예외처리
        if head==None:
            return None
        
        # [1] 일반적인 경우
        
        # 결국 하나씩 순회하면서 순회할때마다 해당 요소를 기록해놔야겠군!
        my_dict = {}
        # key는 index로, val은 ListNode로!
        # key는 ListNode로, val은 index로
        idx = 0
        cur = head # 커서 역할을 해줄 아이 (Do not modify the linked list. 라는 조건 때문에 넣어줌)
        while (cur not in my_dict):
            my_dict[cur] = idx
            idx+=1
            if (cur.next==None):
                return None
            else:
                cur = cur.next
            
        return cur

문제를 풀긴 풀었는데..

퍼포먼스 실화입니까,.,,,ㅋㅋㅋㅋㅋ큐ㅠㅠ 헛웃음뿐,,,,

 

내 두번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # return the node where the cycle begins. If there is no cycle, return null
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # [0] 예외처리
        if head==None:
            return None
        
        # [1] 일반적인 경우
        
        # 결국 하나씩 순회하면서 순회할때마다 해당 요소를 기록해놔야겠군!
        my_set = set()
        # val은 ListNode로!

        cur = head # 커서 역할을 해줄 아이 (Do not modify the linked list. 라는 조건 때문에 넣어줌)
        while not (cur in my_set):
            my_set.add(cur)
            if (cur.next==None):
                return None
            else:
                cur = cur.next
            
        return cur

생각해보니 기존 딕셔너리에서 index는 필요도 없었던거같아서 그냥 딕셔너리가 아닌 set으로 바꿔줌.

(세트의 x in s 연산의 평균 시간 복잡도가 O(1)

파이썬에서는 세트가 해시 테이블(hash table)로 구현되어 있기 때문)

그렇게 하니까 약간 나아지긴 했는데 ㅋㅋㅋ ㅠ.ㅠ.ㅠ.ㅠ 아니 그래도 중간보단 더 잘해야지 ㅠ.ㅠ 

 

재.시.도 ..

요래저래 코드 내 순서들을 바꿔보자

 

내 세번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # return the node where the cycle begins. If there is no cycle, return null
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # [0] 예외처리
        if head==None:
            return None
        
        # [1] 일반적인 경우
        
        # 결국 하나씩 순회하면서 순회할때마다 해당 요소를 기록해놔야겠군!
        my_set = set()
        # val은 ListNode로!

        cur = head # 커서 역할을 해줄 아이 (Do not modify the linked list. 라는 조건 때문에 넣어줌)
        while not (cur in my_set):
            if (cur.next==None):
                return None
            else:
                my_set.add(cur)
                cur = cur.next
            
        return cur

킹받을 정도로 찔끔 올랐음,, (1ms)

 

다시다시!!!!! ㅠ 최소 상위 30퍼는 찍어야집,,,

 

 

나의 네번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # return the node where the cycle begins. If there is no cycle, return null
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # [0] 예외처리
        if head==None:
            return None
        elif head.next==None:
            return None
        
        # [1] 일반적인 경우
        
        # 결국 하나씩 순회하면서 순회할때마다 해당 요소를 기록해놔야겠군!
        my_set = set()
        # val은 ListNode로!

        cur = head # 커서 역할을 해줄 아이 (Do not modify the linked list. 라는 조건 때문에 넣어줌)
        while not (cur in my_set):
            if (cur.next==None):
                return None
            else:
                my_set.add(cur)
                cur = cur.next
            
        return cur

오잉,, 예외처리 쪽에 조건문 하나 더 해서 elif로 처리해줬더니 좀 확 개선됨,,ㅋ,ㅋ,ㅋ,ㅋ,

최대한 예외처리 쪽에서 잡을 수 있는건 미리 잡아야하는가봄,,, (if / elif / else 만 잘좀 활용하면 오히려 시간복잡도 개선엔 더 좋은듯?)

 

 

다섯번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # return the node where the cycle begins. If there is no cycle, return null
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # [0] 예외처리
        if head==None:
            return None
        elif head.next==None:
            return None
        
        # [1] 일반적인 경우
        
        # 결국 하나씩 순회하면서 순회할때마다 해당 요소를 기록해놔야겠군!
        my_set = set()
        # val은 ListNode로!

        cur = head # 커서 역할을 해줄 아이 (Do not modify the linked list. 라는 조건 때문에 넣어줌)
        
        while cur!=None:
            if cur in my_set:
                break # while loop 탈츌
            else:
                my_set.add(cur)
                cur = cur.next
            
        return cur

흑,, 로직 조금 바꿔봤는데,, 퍼포먼스는 위에꺼랑 완전 똑같,,, 사실 로직도 동일한거나 다름없어서 ㅠ 이해는 되는데 ㅠ

왜 더 개선이 안되지?!?!

 

 

여섯번째 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # return the node where the cycle begins. If there is no cycle, return null
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # [0] 예외처리
        if head==None:
            return None
        elif head.next==None:
            return None
        
        # [1] 일반적인 경우
        
        # 결국 하나씩 순회하면서 순회할때마다 해당 요소를 기록해놔야겠군!
        my_set = set()
        # val은 ListNode로!

        cur = head # 커서 역할을 해줄 아이 (Do not modify the linked list. 라는 조건 때문에 넣어줌)
        
        while cur!=None:
            if cur in my_set:
                return cur
            else:
                my_set.add(cur)
                cur = cur.next
            
        return None

오마이갓~.~ 그냥 break 하고 나와서 cur return 할 필요없이 조건문에 걸리는 그 즉시 cur return 해도 될것같아서 해당 부분 코드 개선해줬더니 상위 8퍼로 퍼포먼스 확 개선됨!!

 

 

 

 

---

참고자료

 

세트가 효율적인 이유 = 해시 테이블

세트의 x in s 연산의 평균 시간 복잡도가 O(1)이 될 수 있는 이유는 간단하다.

파이썬에서는 세트가 해시 테이블(hash table)로 구현되어 있기 때문이다.

 

해시 테이블을 이해하려면 우선 해시 함수를 이해해야 한다. 해시 함수는 임의의 데이터를 인자로 받아, 특정 범위 내의 데이터로 반환하는 함수다. 예를 들어, h(x) = x % 100이라는 함수가 있다면, 어떤 정수가 인자로 들어오더라도 0~99 사이의 숫자를 반환하게 된다.

해시 테이블은 해시 함수를 통해 데이터를 저장하는 자료구조다. 해시 함수를 통해 해싱한 후 나온 결과값을 배열의 인덱스로 사용하여, 해당 위치에 데이터를 저장하는 방식이다. 예를 들어, 아래와 같이 출생년도와 이름이 저장된 데이터가 있다고 하자.

presidents = {
    1789: 'washington', 
    1804: 'franklin', 
    1917: 'kennedy', 
    1942: 'biden'
}

이 데이터를 인자로 받은 값을 100으로 나눈 나머지를 반환하는 해시 함수를 활용하여, 해시 테이블에 저장할 수 있다. 딕셔너리의 첫번째 키인 1789를 100으로 나눈 나머지는 89이므로, 'washington' 데이터는 89번 인덱스에 저장되는 식이다.

(해시 테이블에 대한 자세한 설명은 다음 링크를 참고하도록 하자.)

 

리스트에서는 어떤 값이 리스트에 있는지 확인하려면, 리스트의 값을 일일이 확인해야 한다. 반면 해시 테이블로 구현되어 있는 세트의 경우, 해당 값을 해시 함수에 넣어 인덱스에 접근함으로써, 아주 빠르게 해당 값이 있는지 여부를 확인할 수 있다. 따라서 세트에서 x in s 연산의 평균 시간 복잡도는 O(1)이 된다.

 

물론 세트에서도 최악의 경우 x in s 연산의 시간 복잡도가 O(n)이 될 수 있다. 예를 들어, 위 해시 테이블에서 XX50년도에 태어난 사람의 데이터만을 세트에 넣었다고 해보자. 그렇다면 해시 함수를 통해 50번 인덱스에 접근하더라도, 어차피 모든 데이터가 그 인덱스 배열에 있으므로, 시간 복잡도는 리스트와 같은 O(n)이 된다. 하지만 적절한 해시 함수를 사용할 경우, 이런 상황이 발생할 확률은 매우 적을 것이다.

리스트와 세트는 x in s 연산 이외에 특정 요소를 삭제하는 remove 연산의 시간복잡도도 다르다. 평균적으로 리스트는 O(n)이지만, 세트는 O(1)이다. (x in s 연산에서의 시간복잡도 차이를 이해했다면, 이 차이도 쉽게 이해할 수 있을 것이다.) 따라서 중복되지 않는 값을 저장하는 경우에는, 리스트 대신 세트를 사용하는 것이 훨씬 효율적이다.

 

 

출처:

https://velog.io/@ready2start/Python-%EC%84%B8%ED%8A%B8set%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] 세트(set)의 시간 복잡도

 

 

---

https://leetcode.com/problems/linked-list-cycle-ii/discuss/3274329/clean-codes-full-explanation-floyd-s-cycle-finding-algorithm-c-java-python3

-> 이것도 토끼와 거북이 방식으로 풀 수 있다고 함!!!