2816. Double a Number Represented as a Linked List

Problem : https://leetcode.com/problems/double-a-number-represented-as-a-linked-list

 

Difficulty : Medium

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

---

 

풀이

 

LeetCode 및 백준을 지금껏 파이썬으로 풀어봤는데, 이제는 간간히 Go로도 풀이해보려고 한다.

 

• 생각보다 Go는 재밌고 편리한 언어이고
• 기왕 어떻게 배워둔 김에 이 경험을 어떻게든 유지보존하고 싶고
• Go를 다루며 부족했던 점인 Low level에서의 코드 작성 루틴을 더 개발해보고 싶어서

라는 이유인데...

 

각설하고, 문제로 돌아가보도록 하자. 우선 다음 방식을 떠올릴 수 있을 것이다.

 

• 링크드리스트를 한번 순회하며 현재 저장된 결과를 구한 다음
• 현재 저장된 결과를 * 2하고
• 그 결과를 새로운 링크드리스트에 저장

 

인데, 여기서 제약조건으로 링크드리스트의 길이가 최대 10^4까지 오름을 알 수 있다. 숫자로 처리하려면 저장된 결과를 구하는 데 애로사항이 꽃피니, 리스트 혹은 배열 형태로 저장하여 풀이하는 것이 훨씬 간편하다. 배열로 풀이할 때, 현재 자리수의 결과를 *2하고 만약 10이 넘을 경우 앞 자리수로 받아올림하자.

 

여기서 또 개선점을 떠올려 보자. 새로운 링크드리스트에 저장할 필요가 굳이 있을까? 배열에 새로운 수를 저장할 필요가 있을까? 잘 생각해보면, 2배 계산이므로 결국 현재 자리수의 결과값에 영향을 미치는 자리수는 현재 자리수 및 다음 자리수일 것이다. 2배 계산이므로 기껏해야 현재 자릿수부터의 최댓값은 9999999... 형태일 것이고, 받아올림이 연쇄적으로 일어날 수 없는 구조이다.

 

따라서 풀이를 다시 고쳐쓰면

• 링크드리스트를 한번 순회하며
• 각 저장된 결과를 x2배 계산하고
• 만약 결과가 10 이상일 경우 받아올림으로 이전 노드를 업데이트

로 시간복잡도 O(N), 추가 공간복잡도 O(1)으로 바꾸어 쓸 수 있다.

 

파이썬으로는 다음과 같이 풀이할 수 있다.

 

풀이 코드

# 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]:
        prev = None
        cur = head
        if head.val*2 >= 10 :
            head = ListNode(val = 0, next=head)
            prev = head
        while cur is not None :
            if cur.val*2 >= 10 :
                prev.val += 1
            cur.val = cur.val*2 % 10
            prev, cur = cur, cur.next
        return head

 

 

또한, Golang으로도 비슷하게 풀이하면...

 

 

풀이 코드

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

 
func doubleIt(head *ListNode) *ListNode {
    var (
        cur *ListNode
        prev *ListNode
    )

    cur = head
    if cur.Val * 2 >= 10 {
        head = &ListNode{0, head}
        prev = head
    }

    for {
        if cur == nil {
            break
        }
        if cur.Val * 2 >= 10 {
            prev.Val += 1
        }
        cur.Val = cur.Val * 2 % 10
        prev, cur = cur, cur.Next
    }

    return head
}

 

 

비슷하게 통과하는 걸 볼 수 있다!