[2024] day 128. Leetcode 2487. Remove Nodes From Linked List

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 6일 (월)
Leetcode daily problem

2487. Remove Nodes From Linked List

https://leetcode.com/problems/remove-nodes-from-linked-list/?envType=daily-question&envId=2024-05-06

Problem

연결 리스트 haed가 주어 질 때,
해당 연결리스트의 노드가 오른쪽에 더 큰 값을 갖는 노드가 있다면, 기존에 있는 노드를 제거한다.
마지막으로 수정된 연결리스트를 반환한다.

Solution

stack

주어진 연결리스트에서 각 노드를 순회하면서 해당 노드보다 값이 큰 노드가 있다면 스택에 현재 노드를 저장하는 방식을 사용해 노드를 제거한다.
스택에 저장된 노드들은 현재 노드보다 값이 작거나 같은 순서로 쌓이게 된다.
따라서 스택의 맨 위에 있는 노드는 해당 노드를 포함하여 그 이후의 모든 노드보다 값이 크거나 같다.

스택에 저장된 노드들을 하나씩 꺼내면서, 연결리스트를 역순으로 만드는데 이를 통해서 더 큰 값이 있는 노드를 제거하고 작거나 같은 값이 있는 노드만 남게 된다.

Code

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        stack = []
        
        while cur:
            while stack and stack[-1].val < cur.val:
                stack.pop()
            stack.append(cur)
            cur = cur.next
        
        nxt = None
        while stack:
            cur = stack.pop()
            cur.next= nxt
            nxt = cur
            
        return cur          

Complexicity

시간 복잡도

첫번째 while 루프에서 각 노드를 한 번씩 방문하여 시간복잡도는 노드의 총 수 인 n에 선형적인 O(n)의 시간복잡도가 소요된다.
두번째 while 루프에서 스택에 저장된 노드들을 역순으로 꺼내면서 연결 리스트를 수정하므로 O(n)의 시간이 소요되어, 최종 시간 복잡도는 O(n)이다.

공간 복잡도

스택에는 최대 n개의 노드가 저장될 수 있으므로 공간복잡도는 O(n)이다.