[Algorithm] [중급] Linked List 덧셈
안녕하세요 소프트웨어 엔지니어 최지호입니다.
아래 블로그를 가시면 더욱 많은 정보를 접해보실 수 있습니다.
오늘은 Linked List 덧셈 문제를 풀어보는 시간을 가져보도록 하겠습니다.
Linked List란?
Linked List는 List를 구현하는 방법 중 하나입니다. Linked List 안의 각각 값을 Node라고 부를 때, 각 Node는 자신의 값 그리고 다음 값에 대한 레퍼런스를 가지고 있습니다. 그러므로 시작 Node부터 다음 값에 대한 레퍼런스를 쭉 타고 올라가면 전체 List가 완성이 되는 형식입니다. 예를 들어 Javascript로 구현한 간단한 Linked List는 아래와 같습니다.
// Linked List를 생성하는 함수
let ListNode = function (val, next) {
this.val = val;
this.next = next;
};function example() {
const linkedList =
new ListNode(1,
new ListNode(3,
new ListNode(5,
new ListNode(7, null))));
// node1
console.log(linkedList.val); // 1
// node2
console.log(linkedList.next.val); // 3
// node3
console.log(linkedList.next.next.val); // 5
// node4
console.log(linkedList.next.next.next.val); // 7
}
example();
문제
이번 문제는 Linked List 두 개를 더하여 결괏값을 Linked List로 리턴해주는 문제입니다. n 자리 숫자를 거꾸로 된 Linked List로 구현했을 때 (365 = 5-> 6 -> 3) 두 Linked List의 덧셈 값을 똑같은 거꾸로 된 Linked List로 리턴을 해주는 문제입니다. 조건은 숫자가 0일 때를 제외하면 0부터 시작하는 숫자는 존재하지 않습니다.
이 문제를 푸실 때는 세 가지를 주의하시면 될 것 같습니다. 첫 번째로 숫자가 0일 때를 주의하셔야 하고 두 번째로 두 개의 Linked List의 길이가 다를 때를 주의하셔야 합니다. 마지막으로 Linked List의 각 Node를 더했을 때 x > 10일 경우 올림을 하고 x -10을 해주셔야 한다는 걸 유의하시면 쉽게 푸실 수 있는 문제입니다.
풀이
Javascript로 풀이를 해보도록 하겠습니다.
// Linked List Node를 생성하는 함수
let ListNode = function (val, next) {
this.val = val;
this.next = next;
};
const addTwoNumbers = function (l1, l2) {
let curL1 = l1;
let curL2 = l2;
// 첫번째 Node
let original;
// 제작중인 LinkedList의 현재 Node 값을 들고있을 변수
let curNode;
// 올림 적용여부 (raise === true 일경우 +1)
let raise = false;
while (curL1 || curL2) {
// Node의 null 값을 감안해서 만일 null 이면 0을 더해줍니다.
let l1Val = curL1 && curL1.val ? curL1.val : 0;
let l2Val = curL2 && curL2.val ? curL2.val : 0;
let addition = l1Val + l2Val;
// 전 계선에서 올림값이 있었으면 1을 더해줍니다.
if (raise) {
addition += 1;
raise = false;
}
// 만일 덧셈 값이 9보다크면 올림설정을 해주고 Node 값에서 10을 빼줍니다.
if (addition > 9) {
raise = true;
addition -= 10;
}
// 첫 노드일경우 original에 저장해둡니다.
if (!original) {
original = new ListNode(addition, null);
curNode = original;
} else {
// 첫 Node가 아닐경우 새로운 Node를 생성하고 이전 Node의 next 값에 저장해줍니다
// 추가적으로 현재 Node를 새로운 Node로 지정해줍니다.
const newNode = new ListNode(addition, null);
curNode.next = newNode;
curNode = newNode;
}
// 각 Linked List의 현재 Node를 next 값으로 변경해주는 작업입니다.
curL1 = curL1 && curL1.next ? curL1.next : null;
curL2 = curL2 && curL2.next ? curL2.next : null;
}
// 두 Linked List의 길이를 넘는 올림값이 있을경우 새로운 노드를 붙여줍니다.
if (raise) {
curNode.next = new ListNode(1, null);
}
return original;
};위 코드는 제 방식대로 푼 것이고 조금 더 깔끔한 해설은 아래 링크를 가시면 볼 수 있습니다.
