solution
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
// 앞에서부터 두 노드를 더해가면서
// 1의 자리 부분을 잘라내서 가지고, 10의 자리 부분을 다음으로 넘겨줌.
// 각 노드에는 한 자릿수 밖에 없기 때문에 각각 9까지가 최대값임.
let l1_head = l1;
let l2_head = l2;
let remain = 0;
let linked_list = null;
let result = null;
// 한쪽 리스트라도 존재하면 계속해서 진행
while(l1_head || l2_head){
// l1과 l2가 모두 존재하는 인덱스라면
if(l1_head && l2_head){
const sum = l1_head.val + l2_head.val + remain;
// remain 사용 후 초기화
// 초기화하지 않으면 뒤에 이어질 연산에 영향을 끼칠 수 있음.
remain = 0;
// sum이 10을 넘는 값이라면 1의 자릿수만 저장하고, 10의 자릿수를 다음 노드 연산에 넘겨줌.
if(sum >= 10){
if(linked_list){
// linked_list가 존재하는 상황이라면
// 기존의 linked_list의 next에 현재 생성되는 node의 값을 넣어준 뒤
// linked_list를 변경한다.
linked_list.next = new ListNode(sum % 10, undefined);
linked_list = linked_list.next;
} else {
// linked_list가 존재하지 않는 상황이라면
linked_list = new ListNode(sum % 10, undefined);
// 새로 생성된 node를 result에 저장하는 것으로
// return할 Linked List를 만들어놓는다.
result = linked_list;
}
remain = 1;
if(!l1_head.next && !l2_head.next){
linked_list.next = new ListNode(remain, undefined);
linked_list = linked_list.next;
break;
}
} else {
// sum이 10을 넘지 않는다면 그대로 저장.
if(linked_list){
linked_list.next = new ListNode(sum, undefined);
linked_list = linked_list.next;
} else {
linked_list = new ListNode(sum, undefined);
result = linked_list;
}
}
l1_head = l1_head.next;
l2_head = l2_head.next;
continue;
}
// l1만 존재하는 경우
if(l1_head){
const sum = l1_head.val + remain;
remain = 0;
if(sum >= 10){
if(linked_list){
linked_list.next = new ListNode(sum % 10, undefined);
linked_list = linked_list.next;
} else {
linked_list = new ListNode(sum % 10, undefined);
result = linked_list;
}
remain = 1;
// 한쪽만 존재하는 경우에는 마지막 연산이라면(next null)
// 마지막 node 뒤에 연결해주는 작업이 필요함.
if(!l1_head.next){
linked_list.next = new ListNode(remain, undefined);
linked_list = linked_list.next;
break;
}
} else {
if(linked_list){
linked_list.next = new ListNode(sum, undefined);
linked_list = linked_list.next;
} else {
linked_list = new ListNode(sum, undefined);
result = linked_list;
}
}
l1_head = l1_head.next;
continue;
}
// l2만 존재하는 경우
if(l2_head){
const sum = l2_head.val + remain;
remain = 0;
if(sum >= 10){
if(linked_list){
linked_list.next = new ListNode(sum % 10, undefined);
linked_list = linked_list.next;
} else {
linked_list = new ListNode(sum % 10, undefined);
result = linked_list;
}
remain = 1;
if(!l2_head.next){
linked_list.next = new ListNode(remain, undefined);
linked_list = linked_list.next;
break;
}
} else {
if(linked_list){
linked_list.next = new ListNode(sum, undefined);
linked_list = linked_list.next;
} else {
linked_list = new ListNode(sum, undefined);
result = linked_list;
}
}
l2_head = l2_head.next;
continue;
}
}
return result;
};문제는 정말 간단했으나, 조건을 이리저리 생각하다보니 코드가 상당히 길어졌다.
풀이는 간단하다.
두 개의 Linked List가 있고, 그 둘의 맨 앞부터 합쳐나가면서 새로운 Linked List를 생성한다.
이 때, 각 Linked List의 node는 1의 자리 숫자만을 가질 수 있기 때문에
최대 18(9와 9가 나오는 경우)까지 가질 수 있으므로
같은 인덱스의 node의 합이 10을 넘을 경우,
1의 자리 숫자를 새로운 Linked List의 node에 넣어준다.
10의 자리 숫자는 remain에 담아놓은 뒤, 다음 node가 활용할 수 있게 해준다.
주의 할 것은 remain을 사용한 뒤, 0으로 초기화 해주지 않는다면,
연산이 생각지도 못하게 변경될 수 있다는 것이다. 꼭 사용 후 초기화를 해주자.
나머지는 코드 로직을 따라가면 이해할 수 있다.
추가적인 설명이 필요하다고 생각되는 곳은 linked_list와 result를 왜 분리했는가이다.
result는 전체 Linked List를 나타내는 반면,
linked_list는 next에 다음 node를 할당하여 Linked List를 구성해나가는 역할과
다음 node로의 이동을 통해 계속적인 next 활용을 가능하게 하는 역할을 담당한다.
따라서, 로직적인 부분에서는 linked_list를 사용하되,
반환은 전체 Linked List인 result를 반환하는 것이다.
이 풀이를 작성하면서 상당히 많은 시간을 사용했는데, 다른 분들의 코드를 봐도 이렇다할 방법이 없었다.
왜 이렇게 작성했는지에 대한 설명이 없고 무조건 짧기만한 코드가 대다수였다.
아무래도 이 문제는 어떠한 알고리즘을 사용하는 것이 아닐지도 모르겠다는 생각이 든다.
오히려 자료구조 그 자체를 활용하는 문제가 아니었을까 싶다.
다른 분의 solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
var List = new ListNode(0);
var head = List;
var sum = 0;
var carry = 0;
while(l1!==null||l2!==null||sum>0){
if(l1!==null){
sum = sum + l1.val;
l1 = l1.next;
}
if(l2!==null){
sum = sum + l2.val;
l2 = l2.next;
}
if(sum>=10){
carry = 1;
sum = sum - 10;
}
head.next = new ListNode(sum);
head = head.next;
sum = carry;
carry = 0;
}
return List.next;
};이 분도 필자와 비슷한 로직을 구현하신 것으로 보이는데, 훨씬 간단하게 작성하셨다.
필자는 l1과 l2가 모두 존재하는 경우와 각각 존재하는 경우를 나눴으나,
그럴 필요 없이 l1이 존재할 때에 대해 연산, l2가 존재할 때에 대한 연산을 해주면 됐었다..
그 외 로직은 필자와 동일하다.
필자의 변수 remain이 여기서는 carry가 되었다는 점이 다르다.
공통적인 코드를 너무 많이 작성했다는 점과 분기를 나누지 않아도 되는 부분까지 처리했다는 점이
필자의 코드를 길게 만들어 버린게 아닐까 싶다.
