Add Two Numbers
문제 개요
주어지는 자료형태는 Linked-List 이다. 리스트의 특성에 따라 여러 개의 데이터를 담을 수 있고 각각의 저장되어있는 데이터는 List-Node라고 한다.
List-Node에는 0~9의 숫자가 들어올 수 있다. 음수나 10 이상의 숫자는 들어올 수 없다.
Linked-List에 저장하려는 값은 100자리 이하의 긴 숫자이다. 저장 형태는 원래 숫자의 역순으로 저장되어 있다.
두 개의 Linked-List 'l1', 'l2'가 주어졌을 때, l1 과 l2에 저장되어있는 숫자를 합한 결과의 Linked-List를 구해야 한다.
입,출력 예
Example 1:
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]
이해한 부분
-
Linked-List가 주어지고 역순으로 각 자릿수의 숫자(0~9)를 저장한다.
-
우리의 목표는 두 개의 Linked-List를 더한 결과의 Linked-List를 구해야 한다.
문제에서 어려웠던 부분
-
자릿수가 넘어갈 때 처리하는 방법
-
각 더한 자릿수를 다시 역순으로 저장하는 방법
해결 전략
바로 떠올린 방법
1. l1의 sum을 구한다. (sum_l1) O(len(l1))
2. l2의 sum을 구한다. (sum_l2) O(len(l2))
3. sum_l1 + sum_l2를 구한 후 O(1) 그걸 Linked-List를 역순으로 저장한다. O(sum_l1+sum_l2의 자릿수)
심사숙고 하여 해결한 방법
1. 각 Linked-List의 현재 위치를 저장하는 변수 할당 (pointer1, pointer2 : 초기 값은 각 list의 head)
2. 아래의 case를 바탕으로 각 Node를 더한다.
- pointer1 != null && pointer2 != null
- pointer1 != null
- pointer2 != null
3. 더했을 때 10이 넘어갈 경우 10의 자리 수를 임시로 저장한 후 다음 계산에 포함하기 (carry : 초기 값은 0)
- sum = (pointer1.val + pointer2.val + carry) % 10
- carry = (pointer1.val + pointer2.val + carry) / 10
4. Linked-List를 역순으로 저장하도록 함 --> 이게 잘 안먹힘
static ListNode addNodeReverseOrder(ListNode output, int val) {
ListNode newNode = new ListNode(val);
if (output == null) {
return newNode;
}
newNode.next = output;
return newNode;
}
결과
List가 역순이 아닌 정배열로 저장됨
회고
개념을 쌓기 위해 포인터 지정, 저장 방식(정배열, 역배열)을 외워야 하는 것 처럼 보인다. 아래의 내용을 외우자.
정배열 저장
def AddFrontNode():
dummy = ListNode()
currentNode = dummy
while target: # target is not None
currentNode.next = ListNode(target.value)
currentNode = currentNode.next
target = target.next
return dummy.next
역배열 저장
def AddBackNode():
currentNode = None
while target: # target is not None
newNode = ListNode(target.value)
newNode.next = currentNode
currentNode = newNode
target = target.next
return currentNode