[Leetcode]2. Add Two Numbers
문제 : 두 개의 비어있지 않은 연결 리스트가 주어집니다. 이 리스트들은 각각 하나의 비음수 정수를 나타내며, 각 노드는 한 자리 숫자를 포함하고 있습니다. 숫자는 역순으로 저장되어 있습니다. 두 숫자를 더한 후, 그 합을 연결 리스트로 반환하세요.
두 숫자는 숫자 0 자체를 제외하고는 앞에 0이 포함되어 있지 않다고 가정할 수 있습니다.
예시 :
즉, 두개의 연결 리스트가 주어지고, 그 연결 리스트를 처음 tail부터 head까지(역순) 연속된 노드들을 이어 정수를 만들고, 그 두 값을 더해 새로운 연결 리스트로 리턴 해야한다.
1. 처음 나의 생각 :
일단 연결 리스트가 주어졌고, 위의 예시 첫번째를 보면 2 -> 4 -> 3이다. 이 연결 리스트를 뒤에서부터 읽으면 342이다. 자 그럼, 이 연결 리스트를 어떻게 342라는 정수로 표현 할 수 있을까?
342 = 300 + 40 + 2
즉, 초기 자릿수 값을 1로 설정하고, 노드를 넘어갈 때마다 그 자릿수에 10을 곱해 정수를 만든다. 예를 들어, head부터 읽으면 2가 읽힐것이다. 이때, 2와 초기 자릿수값 1을 곱해 sum1(첫번째 인자로 주어지는 연결리스트의 합)이라는 변수에 2를 더하고, 그 다음 노드로 넘어가면 4를 읽고, 이 4와 업데이트된 자릿수 값 10을 더해 40을 sum1에 더한다.(2 + 40 = 42) 마지막으로, 그 다음 노드의 값인 3을 읽어와 업데이트된 자릿수 값 100이랑 곱한다(300 + 40 + 2).
두번째 연결리스트 인자도 같은 방식으로 총합을 계산 한 후, 총합이 1보다 클때까지 나머지 연산(modulo)를 이용해 각 자릿수의 값을 가져온다. 그 다음, 그 값을 다시 새로운 연결 리스트에 담아 반환한다.
코드는 아래와 같다.
/**
* 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) {
ListNode dummy = new ListNode(0);
ListNode rCurrent = dummy;
ListNode current = l1;
ListNode current2 = l2;
int l1Sum = 0;
int l2Sum = 0;
int digit = 1;
int digit2 = 1;
while(current != null) {
l1Sum += current.val * digit;
current = current.next;
digit *= 10;
}
while(current2 != null) {
l2Sum += current2.val * digit2;
current2 = current2.next;
digit2 *= 10;
}
int total = l1Sum + l2Sum;
if (total == 0) {
return new ListNode(0);
}
while(total > 0) {
int digits = total % 10;
rCurrent.next = new ListNode(digits);
rCurrent = rCurrent.next;
total /= 10;
}
return dummy.next;
}
}
일단 여기서 연결 리스트와 관련된 궁금증 몇가지를 풀고 가 보자.
- dummy : 말 그대로 연결 리스트의 첫번째 값을 참조하기 위해 만든 임시 노드이다. 생성자에 0을 넘겨, 그냥 임시 노드(시작노드)를 만든 것이다. 이 dummy는 나중에 최종 연결 리스트를 반환할때 사용된다. 예를들어, 우리가 만약 1->2->3을 반환해야 한다면, dummy노드를 이용해 0->1->2->3 와 같은 연결 리스트를 만들고, 앞의 0을 제외한 나머지 1->2->3 을 반환해주면 된다.
- dummy.next : 왜 next를 반환할지부터 생각 해 보자. 맨 처음에 dummy 노드는 노드의 값을 0으로 초기화 해 주었다. 하지만 이 더미 노드는 말 그대로 노드의 시작점을 참조하기 위해 우리가 임의로 만든 것이고, 여기에 dummy.next를 하면 뒤의 값이 모두 반환된다. 연결 리스트의 특징 :. .next로 다음 노드를 참조하면, 다음 노드 뿐만 아니라 next로 연결되어있는 노드까지 모두 반환한다.
하지만... 기본적인 테스트 케이스 몇개를 제외하곤 너무나도 많은 테스트 케이스를 통과하지 못 했다. 문제를 보니,,, 테스트 케이스로 준 연결 리스트는 제일 긴 총 합이 899,999,999였다. 그런데 테스트 케이스는 int로 커버가 불가능한 long의 영역까지 커버해야하는것을 알고, 형 변환을 해 주었다. 하지만 이번에는 1884개의 테스트중 3개의 테스트가 또 다시 fail하였다. 문제를 보니 이건 int나 long의 문제가 아니였다. 내가 너무 단순한 수학적인 방식으로 풀려고 했기 때문에 실패했던 것이였다.
2. 두번째 생각 : 그럼 type문제를 아예 빼놓고, 이 문제를 어떻게 해결 할 수 있을까?
아이패드에 연결 리스트 그림을 그려놓고 보니, 그냥 각 자릿수의 노드들을 서로 더해 같은 자릿수에 넣어주면 되는 것이였다... 굳이 복잡하게 일일히 1, 10, 100을 곱해주면서까지 정수를 만들고, 그 정수들을 다시 더하고 나머지 연산을 하는 등 복잡한 로직은 전혀 필요하지 않았다.
예를들어, 2->4->3 && 5->6->4는 (2+5) (4+6) (3+4)를 각각 그에 맞는 자릿수에 넣어주면 됐다. 하지만 여기서 문제가 하나 생긴다. 가운데 4 +6 처럼 더한 값이 10이 넘어버리면 어떻게 해야 할까?(당연히 손으로 덧셈을 하면 어떻게 해야할지 안다. 하지만 이걸 코드로 어떻게 풀어낼까?)
1. 'carry'라는 변수를 사용해 두 정수의 합이 10이 넘는지 안 넘는지 판단한다.
/**
* 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) {
ListNode dummy = new ListNode(0);
ListNode rCurrent = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10;
rCurrent.next = new ListNode(sum % 10);
rCurrent = rCurrent.next;
}
return dummy.next;
}
}
위의 코드를 보면 내가 처음 생각했던 코드보다 훨씬 간결하고 가독성이 좋다.
- 먼저, 처음과 같이 dummy를 0으로 초기화해 임시 노드를 만들고, current를 더미를 가리키도록 한다. 그 다음 내가 언급했던 carry(올림수)를 0으로 초기화 한다.
- int sum = carry : 이전 계산에서 두 정수의 합이 10이 넘었는지 확인하고, 넘었다면 다음 덧셈값에 이 carry(올린 자릿수)를 추가로 더해준다. 예를들어, 예를 들어보자.
- 첫번째 while loop : sum은 0으로 초기화 되어있다. 이 sum에다가 각 연결 리스트의 head값인 2 + 5를 해 준다. 그럼 7이고, 7은 10을 넘지 않으므로 carry의 값은 7 / 10으로 0.7이지만, 자바에서의 int는 정수 뒤의 소수점을 무시하므로 첫번째 while에서는 carry의 값이 0이 된다. 그 다음, dummy node의 다음 노드값으로 결과값을 넣어준다. 7 % 10은 7 임으로 현재 결과노드는 이렇게 생겼다. 0 -> 7.
- 두번째 while loop : sum은 다시 0으로 초기화 된다. 첫번째 while loop에서 10을 넘지 않았기 때문이다(== carry가 0임.). 이제 노드의 두번째 값들을 서로 더해준다. (4 + 6) 그러면 sum은 10이 되지만, carry 10/10에서 carry는 1이 된다. 여기서 1은 이제 다음 sum에서 올려줘야 할 값이다. 그 다음 10 % 10 = 0를 결과 노드에 다음 노드로 추가 해 준다.
- 세번째 while loop : sum은 0이 아니라 1로 초기화 된다(이전 while loop에서 올림값). 이제 각 연결 리스트의 마지막 값들을 더해준다. (4+3) 하지만 여기에다가 우리가 10이 넘어 올라온 올림값 1을 더해 8로 만들어 준다. 이제 이 8을 마지막 결과 노드로 넣어주면 우리가 원하는 값을 얻을 수 있다.
이렇게 문제를 풀고 나니 느낀점 : 처음부터 코드를 다짜고짜 써 내려 갈 생각을 하지 말고, 문제를 좀 더 꼼꼼히 보고 종이와 펜을 준비해 어떠한 다른 방법이 있는지부터 천천히 살펴보자.