하루에 한 문제씩 풀기 시작했다. 언제까지 할 지는 모르겠다. 불친절할지도 모른다. 그래도 부끄러운 내 코드를 박제해둔다는 마음으로 써 가야겠다.
첫 번째 시도
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# calculate number
l1_num = 0
l1_remain = 0
# start with zero
while l1.val == 0:
l1_remain += 1
l1 = l1.next
if l1 == None:
break
while l1 != None:
l1_num = l1_num*10 + l1.val
l1 = l1.next
l2_num = 0
l2_remain = 0
while l2.val == 0:
l2_remain += 1
l2 = l2.next
if l2 == None:
break
while l2 != None:
l2_num = l2_num*10 + l2.val
l2 = l2.next
ret_num = int(str(l1_num)[::-1])*(10**l1_remain) + int(str(l2_num)[::-1])*(10**l2_remain)
# convert number to ListNode
ret = ListNode()
s = ret
while ret_num != 0:
s.val = ret_num % 10
ret_num //= 10
if(ret_num == 0):
break;
s.next = ListNode()
s = s.next
return ret문제를 제대로 이해하지 못해서 돌아가서 푼 것 같다. 처음에는 계산되는 숫자들은 정방향이고, 계산값은 다시 반대로 표시하라고 이해한 결과. 숫자를 뒤집어야 하기 때문에 숫자를 뽑아서 뒤집고, 0으로 시작하는 경우를 예외로 두었다. 그래도 절반을 이겼다.
Beats 53.85%
두 번째 시도
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
ret = ListNode()
remain = 0
s = ret
while l1 != None or l2 != None:
if l1 == None:
s.val = (l2.val + remain) % 10
remain = (l2.val + remain) // 10
s.next = ListNode()
s = s.next
l2 = l2.next
continue
if l2 == None:
s.val = (l1.val + remain) % 10
remain = (l1.val + remain) // 10
s.next = ListNode()
s = s.next
l1 = l1.next
continue
s.val = (l1.val + l2.val + remain) % 10
remain = (l1.val + l2.val + remain) // 10
s.next = ListNode()
s = s.next
l1 = l1.next
l2 = l2.next
return ret더 간단해졌으나, 마지막에 더미 노드를 추가하게 되어 항상 끝에 0이 붙게 되었다. 그리고 용기내기로 한 뒤 5분만에 부끄러워졌다. != None은 도대체 뭘까? 마지막으로 코드를 쓴 게 1년 정도 전이라는 변명을 해본다.
두 번째 시도 개선 1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
ret = ListNode()
remain = 0
s = ret
while l1 or l2:
l1_val = l1.val if l1 else 0
l2_val = l2.val if l2 else 0
sum = l1_val + l2_val + remain
remain = sum // 10
s.next = ListNode(sum % 10)
s = s.next
if l1: l1 = l1.next
if l2: l2 = l2.next
if remain > 0:
s.next = ListNode(remain)
return ret.nextgpt한테 물어봤다. l1과 l2의 예외처리, next에 값을 넣고, ret.next를 반환하는 방식으로 문제를 해결했다. 그런데 문제가 있었다. 분명히 마지막 코드가 더 예쁜데, 내 예쁜 코드는 더 약해졌다.
Beats 18.85%
두 번째 시도 개선 2
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
res = dummy
total = carry = 0
while l1 or l2 or carry:
total = carry
if l1:
total += l1.val
l1 = l1.next
if l2:
total += l2.val
l2 = l2.next
num = total % 10
carry = total // 10
dummy.next = ListNode(num)
dummy = dummy.next
return res.next같은 논리 구조를 가지고 있으나 더 빠른 코드. 삼항연산자를 없애 더 단순화시켰고, carry를 따로 처리하지 않고 l1, l2와 같이 한번에 조건을 확인한다.
Beats 71.82%
가장 빠른 코드
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
sum_node_head = ListNode()
ptr = sum_node_head
sum = 0
while l1 or l2 or sum > 0:
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next
if sum > 9:
sum -= 10
ptr.next = ListNode(sum)
ptr = ptr.next
sum = 1
else:
ptr.next = ListNode(sum)
ptr = ptr.next
sum = 0
return sum_node_head.nextsum에 대한 처리를 더 최적화했다. 나머지가 2 이상일 경우는 없으니 나머지 계산을 하지 않고 뺄셈으로 바꾸어 다루었다. 근데 내가 제출해보니 또 상위권으로 나오지는 않는다. 어떻게 정하는건지를 모르겠다.
Beats 53.85%
마무리
단순히 코드와 방법을 읊는 것 보다는 이런 게 더 낫지 않을까 생각해서 주저리 주저리 해 보았다. 개인사정이자 게으름으로 오랫동안 코드를 작성하지 못했는데 오랜만에 작성해보니 새록새록 기억이 난다. 어떻게든 써지는 게 신기했다. 제발 이번에는 꾸준히 한 문제씩 풀 수 있기를.
