참고
문제해설
NOTE
•
입력값 ⇒ 2개의 음수를 포함하지 않고 비어있지 않은 정수 배열
•
출력값 ⇒ 2개의 정수 배열을 차례로 더한 정수 배열
문제 로직고민
NOTE
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
}
Java
복사
주어진 ListNode의 형식
•
노드의 val이 0~9이므로 매개변수로 주어진 node를 순차적으로 순회하면서, 값을 채워나간다.
◦
2개의 node를 더한값이 10을 넘어서면 저장할때는 %10의 값을 저장하고 , 다음 저장값에 +1을한다.
◦
2개의 배열 중 하나를 모두 탐색하면, 나머지 정수 배열 하나의 남은값을 모두 탐색한다.
◦
2개의 배열을 모두 탐색했는데, 다음 저장값 +1이 남아있다면 val 1의 ListNode를 넣어준다.
•
반환값은 처음 ListNode이다. 처음 ListNode를 어떻게 가지고 있을것인가?
◦
처음에 이를 어떻게 지정할지 조금 고민했는데, 그냥 최초에 firstNode를 만들고, null값이면 생성된 ListNode를 넣어주었다.
작성코드
NOTE
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int next = 0;
int data = 0;
ListNode prevNode = new ListNode();
ListNode curNode = null;
ListNode firstNode = null;
// 2개의 배열이 모두 완전히 탐색되지 않았다.
while(l1 != null && l2 != null){
data = l1.val + l2.val + next;
curNode = new ListNode(data%10);
if(firstNode == null) firstNode = curNode;
prevNode.next = curNode;
prevNode = curNode;
if(data >= 10) next = 1;
else next = 0;
l1 = l1.next;
l2 = l2.next;
}
// l1의 배열이 모두 탐색되지 않았다.
while(l1 != null){
data = l1.val + next;
curNode = new ListNode(data%10, null);
prevNode.next = curNode;
prevNode = curNode;
if(data >= 10) next = 1;
else next = 0;
l1 = l1.next;
}
// l2의 배열이 모두 탐색되지 않았다.
while(l2 != null){
data = l2.val + next;
curNode = new ListNode(data%10, null);
prevNode.next = curNode;
prevNode = curNode;
if(data >= 10) next = 1;
else next = 0;
l2 = l2.next;
}
// 2개의 배열이 모두 탐색되었는데 증가분이 남아있다.
if(next == 1){
curNode = new ListNode(1, null);
prevNode.next = curNode;
prevNode = curNode;
}
return firstNode;
}
}
Java
복사
정답코드
NOTE
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
var sum = sumLists(l1, l2, 0);
System.gc();
return sum;
}
public ListNode sumLists(ListNode l1, ListNode l2, Integer more) {
if (l1 == null && l2 == null && more == null) {
return null;
}
if (more == null) {
more = 0;
}
if (l1 != null) {
more += l1.val;
l1 = l1.next;
}
if (l2 != null) {
more += l2.val;
l2 = l2.next;
}
if (more > 9) {
return new ListNode(more - 10, sumLists(l1, l2, 1));
}
return new ListNode(more, sumLists(l1, l2, null));
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
메모리가 하위 8%이길래 코드를 너무 막 사용했는가 싶었는데, 3MB밖에 차이 안나서 다행이다.
•
재귀함수를 사용해서 내가 작성한 코드보다 훨씬 간결하게 작성한게 눈에 뛰는거 같다.
•
로직자체는 크게 차이나 보이지는 않는다.