[2024] day 129. Leetcode 2816. Double a Number Represented as a Linked List

gunny·2024년 5월 7일

Leetcode 2816. Double a Number Represented as a Linked List Leetcode 2816. Double a Number Represented as a Linked List python

코딩테스트

목록 보기

443/530

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

2024년 5월 7일 (화)
Leetcode daily problem

2816. Double a Number Represented as a Linked List

https://leetcode.com/problems/double-a-number-represented-as-a-linked-list/?envType=daily-question&envId=2024-05-07

Problem

앞에 0이 없는 음수가 아닌 정수를 나타내는 비어 있지 않은 연결형 리스트의 head가 제공 될때, 해당 노드의 값을 2배로 늘린 후에 연결 리스트의 head를 반환한다.

Solution

Two Pointers

처음에 접근한 방식은 연결 리스트를 순환해서 해당 노드의 val 값을 파악하고, 해당 val 값에 2를 곱한 후에 나온 최종 값을 이용해 연결형 리스트를 다시 만들어서 반환하는 것이었는데 ValueError인 Runtime Error가 발생했다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        val = ''
        
        while head:
            val += str(head.val)
            head = head.next
            
        finalVal = int(val) * 2
        val_list = list(str(finalVal))
        
        
        ans = ListNode(val_list[0])
        dummy = ans
        for i in range(1, len(val_list)):
            dummy.next = ListNode(val_list[i])
            dummy = dummy.next
            
        return ans

다른 접근 방법으로는 Two Pointers 를 사용하는 것이다.
이 접근 방법은 이전 노드의 값에 대한 일부 컨텍스트를 유지하는 것인데, 현재 노드를 탐색하면서 2배를 해주는 과정에서 해당 값이 10의 자리 이상의 값이 나온 경우, 이전 노드의 값을 업데이트 하는 것이다.

"prev"과 "cur"라는 두 가지 포인터를 사용해야 하는데, "prev" 포인터는 이전 노드를 추적하고, "cur" 포인터는 처리 중인 노드를 가리킨다.

각 노드에 대해 값을 두 배로 늘리고 필요한 경우 이전 노드의 값을 업데이트하는 과정을 반복한다.

이 때 연결된 목록의 각 노드를 처리할 때 고려해야 할 세 가지 사례를 구현해야 하는데
(1) 두 배의 값이 10보다 작은 경우:
현재 노드의 값은 단순히 두 배의 값으로 대체한다.
(2) 두 배의 값이 10보다 크거나 같은 경우:
현재 노드의 값은 두 배의 값의 나머지(모듈로 10)로 대체되고 이전 노드의 값은 캐리를 반영하여 업데이트한다.
(3) 첫 번째 노드의 값을 업데이트해야 하는 경우:
첫 번째 노드의 두 배가 된 값이 10보다 크거나 같으면 값이 1인 새 노드가 생성되고 이 노드가 목록의 새 헤드로 업데이트한다.

이러한 접근 방식으로 연결된 목록의 각 노드를 적절하게 처리한다.

Code

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        prev = None
        
        while cur:
            val = cur.val*2
            if val < 10:
                cur.val = val
            elif prev:
                cur.val = val%10
                prev.val +=1
            else:
                head= ListNode(1, cur)
            
            cur.val = val%10
            prev = cur
            cur = cur.next
        
        return head