이때 푼 풀이에서는 숫자를 다루다보니 소숫점이 많아지면 값이 미묘하게 달라져서 스트링으로 취급해봄 : https://greedydeveloper.tistory.com/64
Given Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the .two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Submitted Code
# 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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
l = list(map(int, str(r3)))
l = list(reversed(l))
#l.pop() 여기나 index에서 처리하면 마지막 숫자가 사라지고 그냥 0이 그자리로 감
res = ListNode()
temp = res;
for i in range(len(l)):
temp.val = l[i]
temp.next = ListNode()
temp = temp.next
#res = res.next 하면 맨 앞이 사라짐 맨 뒤가 아니라 ㅋ
temp = res;
while(temp.next.next):
temp = temp.next
temp.next = None
return res;
The way I reached to a solution
# 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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
res = ListNode()
temp = res;
while (r3 > 0):
temp.val=r3%10
r3 = r3 - r3%10
r3 = int(r3/10)
temp.next = ListNode()
temp = temp.next
return res;
Input
l1 =
[2,4,3]
l2 =
[5,6,4]
Output
[7,0,8,0]
Expected
[7,0,8]
Input
l1 =
[9,9,9,9,9,9,9]
l2 =
[9,9,9,9]
Output
[8,9,9,9,0,0,0,1,0]
Expected
[8,9,9,9,0,0,0,1]
Input
l1 =
[0]
l2 =
[0]
Output
[0]
Expected
[0]
something / 0 형태로 들어갔을텐데 왜 에러가 안 나고 다음에 0이 하나 더 나오는지는 의문 int()로 처리해서 그런가
아무튼 0으로 안 나누도록 아래처럼 바꿈 나는 0으로 나누면 0되는줄 알았는데
# 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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):as
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
res = ListNode()
temp = res;
while (True):
temp.val=r3%10
r3 = r3 - r3%10
if(r3==0):
break;
r3 = int(r3/10)
temp.next = ListNode()
temp = temp.next
return res;
Wrong Answer 1565 / 1568 testcases passed
Input
l1 =
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
l2 =
[5,6,4]
1565 / 1568 testcases passed
Output
[6,6,2,2,4,4,2,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
Expected
[6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
r3 = int(r3/10)이 숫자가 커지면 소숫점이 밀리면서 문제 생기는듯…
- math.ceil() : 소수 부분을 정수로 올려, integer로 만듭니다.
- math.floor() : 소수 부분을 버리고, integer로 만듭니다.
# 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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
res = ListNode()
temp = res;
while (True):
temp.val=r3%10
r3 = r3 - r3%10
if(r3==0):
break;
r3 = math.floor(r3/10)
temp.next = ListNode()
temp = temp.next
return res;
Wrong Answer
Input
l1 =
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
l2 =
[5,6,4]
1565 / 1568 testcases passed
Output
[6,6,2,2,4,4,2,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
Expected
[6,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
res = ListNode()
temp = res;
l = list(map(int, str(r3)))
l = list(reversed(l))
for i in range(len(l)):
temp.val = l[i]
temp.next = ListNode()
temp = temp.next
return res;
Input
l1 =
[9,9,9,9,9,9,9]
l2 =
[9,9,9,9]
Output
[8,9,9,9,0,0,0,1,0]
Expected
[8,9,9,9,0,0,0,1]
왜 하나가 더 나갈까요 생각해보자
일단 맨뒤의것 하나 삭제하는 방법을
안되네요 ㅋ
print ("test")
L1 = [2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
l1 = makeListNode( L1)
printListNode(l1)
L2 = [5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]
l2 = makeListNode(L2)
printListNode(l2)
addTwoNumbers(l1, l2)
Input
l1 =
[2,4,3]
l2 =
[5,6,4]
Output
[7,0,0]
Expected
[7,0,8]
테스트 돌렸더니 이렇게된
# Definition for singly-linked list.
from ast import List
import math
class ListNode:
def __init__(self,val=0, next=None):
self.val = val
self.next = next
class Solution:
def main():
def makeListNode( l:List):
res = ListNode()
temp = res
for i in range(len(l)):
temp.val = l[i]
temp.next = ListNode()
temp = temp.next
return res;
def printListNode( l:ListNode):
temp = l
while (temp.next != None):
print(temp.val)
temp = temp.next
else:
print(temp.val)
def addTwoNumbers( l1:ListNode, l2: ListNode):
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
print("r1:")
print(r1)
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
print("r2:")
print(r2)
r3 = r1 + r2
print("r3:")
print(r3)
#write
res = ListNode()
temp = res;
l = list(map(int, str(r3)))
l = list(reversed(l))
#l.pop() 여기나 index에서 처리하면 마지막 숫자가 사라지고 그냥 0이 그자리로 감
for i in range(len(l)):
temp.val = l[i]
print("temp.val")
print(l[i])
temp.next = ListNode()
temp = temp.next
return res;
print ("test")
L1 = [2,4,3]
l1 = makeListNode( L1)
printListNode(l1)
L2 = [5,6,4]
l2 = makeListNode(L2)
printListNode(l2)
res = addTwoNumbers(l1, l2)
print("res")
printListNode(res)
if __name__ == "__main__":
main()
# Definition for singly-linked list.
from ast import List
import math
class ListNode:
def __init__(self,val=0, next=None):
self.val = val
self.next = next
class Solution:
def main():
def makeListNode( l:List):
res = ListNode()
temp = res
for i in range(len(l)):
temp.val = l[i]
temp.next = ListNode()
temp = temp.next
return res;
def printListNode( l:ListNode):
temp = l
while (temp.next != None):
print(temp.val)
temp = temp.next
else:
print(temp.val)
def addTwoNumbers( l1:ListNode, l2: ListNode):
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
print("r1:")
print(r1)
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
print("r2:")
print(r2)
r3 = r1 + r2
print("r3:")
print(r3)
#write
res = ListNode()
temp = res;
l = list(map(int, str(r3)))
print("r3 to list l")
print(l)
l = list(reversed(l))
#l.pop() 여기나 index에서 처리하면 마지막 숫자가 사라지고 그냥 0이 그자리로 감
print("reverse l")
print(l)
for x in l:
temp.val = x
print("temp.val")
print(x)
temp.next = ListNode()
temp = temp.next
return res;
print ("test")
L1 = [2,4,3]
l1 = makeListNode( L1)
printListNode(l1)
L2 = [5,6,4]
l2 = makeListNode(L2)
printListNode(l2)
res = addTwoNumbers(l1, l2)
print("res")
printListNode(res)
if __name__ == "__main__":
main()
test 2 4 3 0 5 6 4 0 r1: 342 r2: 465 r3: 807 r3 to list l [8, 0, 7] reverse l [7, 0, 8] temp.val 7 temp.val 0 temp.val 8 res 7 0 8 0
# 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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
l = list(map(int, str(r3)))
l = list(reversed(l))
#l.pop() 여기나 index에서 처리하면 마지막 숫자가 사라지고 그냥 0이 그자리로 감
res = ListNode()
temp = res;
for i in range(len(l)):
temp.val = l[i]
temp.next = ListNode()
temp = temp.next
#res = res.next 하면 맨 앞이 사라짐 맨 뒤가 아니라 ㅋ
temp = res;
beforeTemp = res;
while(temp.next != None):
temp = temp.next
beforeTemp = temp
beforeTemp.next = None
return res;
Output
[7,0,8,0]
Expected
[7,0,8]
Remove last node of the linked list
temp = res;
beforeTemp = res;
while(temp.next != None):
temp = temp.next
beforeTemp = temp
beforeTemp.next = None
응 개뿔도 안됨
Algorithm:
If the first node is null or there is only one node, then they return null. ◦ if headNode == null then return null ◦ if headNode.nextNode == null then free ◦ head and return nullCreate an extra space secondLast, and traverse the linked list till the second last node. ◦ while secondLast.nextNode.nextNode != null secondLast = secondLast.nextNode delete the last node, i.e. the next node of the second last node delete(secondLast.nextNode), and set the value of the next second-last node to null.
저랑 똑같이 하셨는데요
# Function to remove the last node
# of the linked list
def removeLastNode(head):
if head == None:
return None
if head.next == None:
head = None
return None
second_last = head
while(second_last.next.next):
second_last = second_last.next
second_last.next = None
return head
T.T it’s the same way with me
she put None to second_last.next
oh wait I could do secondLast.next.next I didn’t know that
and I didn’t have to put a = in while condition bc it’s true when it’s not None
temp = res;
while(temp.next.next):
temp = temp.next
temp.next = None
return res;
wait it works
so what’s the difference between
this
temp = res;
while(temp.next.next):
temp = temp.next
temp.next = None
and this
temp = res;
beforeTemp = res;
while(temp.next != None):
temp = temp.next
beforeTemp = temp
beforeTemp.next = None
should i put None to beforetemp? but it doesn’t make sense?
it was bc I put temp = temp.next before I put beforeTemp = temp
which means beforeTemp == temp
what I wanted to do was
temp = res;
beforeTemp = res;
while(temp.next != None):
beforeTemp = temp
temp = temp.next
beforeTemp.next = None
.
# 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]:
# read
temp = l1;
r1=0;
i1 = 1;
while (temp.next != None):
r1 = r1 + (i1)*temp.val
i1=i1*10
temp = temp.next
else:
r1 = r1 + (i1)*temp.val
temp = l2;
r2=0;
i2 = 1;
while (temp.next != None):
r2 = r2 + (i2)*temp.val
i2=i2*10
temp = temp.next
else:
r2 = r2 + (i2)*temp.val
r3 = r1 + r2
#write
l = list(map(int, str(r3)))
l = list(reversed(l))
#l.pop() 여기나 index에서 처리하면 마지막 숫자가 사라지고 그냥 0이 그자리로 감
res = ListNode()
temp = res;
for i in range(len(l)):
temp.val = l[i]
temp.next = ListNode()
temp = temp.next
#res = res.next 하면 맨 앞이 사라짐 맨 뒤가 아니라 ㅋ
temp = res;
while(temp.next.next):
temp = temp.next
temp.next = None
return res;
'Coding Test' 카테고리의 다른 글
| 4. Median of Two Sorted Arrays (0) | 2023.07.20 |
|---|---|
| 3.Longest Substring Without Repeating Characters (0) | 2023.07.20 |
| 1.1 Two Sum 파생문제(자작) (2) | 2023.01.02 |
| 1.Two Sum (0) | 2023.01.02 |
| 프로그래머스 행렬의 덧셈 (0) | 2021.08.09 |
