두 개의, 비어있지 않은 linked list들이 입력으로 주어지고,
각각의 리스트에는 음수가 아닌 정수가 담긴다.
numbers들은, 역순으로 저장이 되어 있고, 각 노드는 하나의 숫자만을 저장하고 있다.
가장 큰 자릿수에 0은 오지 않는다 (단, 0 하나만 담긴 linked list는 가능하다)
저장된 숫자를 더하고, 이를 다시 linked list에 담아서 return 하는 문제
Example)
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
2,4,3의 역순은 342가 되고, 5,6,4의 역순은 465 이므로,
둘을 합한 결과인 807을 다시 역순으로 linked list에 담아서 저장하면 된다.
제한사항:
node의 값으로는 0~9만이 올 수 있으며,
linked list의 크기는 1~100이다.
/**
* 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; }
* }
*/
import java.math.BigInteger;
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
BigInteger big = new BigInteger(backnumber(l1)).add(new BigInteger(backnumber(l2)));
String [] box = big.toString().split("");
ListNode temp = new ListNode();
ListNode result = recover(box, temp);
return result;
}
public String backnumber(ListNode lst){
if(lst == null){
return "";
}
return backnumber(lst.next)+ Integer.toString(lst.val);
}
public ListNode recover(String [] temp, ListNode lst){
int length = 0;
lst = new ListNode(Integer.parseInt(temp[length]));
length += 1;
while(length < temp.length) {
lst = new ListNode(Integer.parseInt(temp[length]), lst);
length += 1;
}
return lst;
}
}새벽 3시 반 쯤에 깨서 아침 8시가 되어서야 겨우 Success 초록색을 볼 수 있었다.
LeetCode에서 Recursion 태그가 달린 문제 중 첫번째 문제였다.
풀면서 아직 재귀 문제에 익숙하지 않음을 뼈저리게 확인할 뿐이었다.
우선, backnumber 함수를 구현해서, input의 linked list에 담긴 각 숫자들을
역순으로 호출하여, int로 return 했다 (이것이 뼈저리게 큰 실수였음은, 1시간 반 뒤에나 깨닫게 된다)
이제껏 재귀나 dfs 문제를 풀 때, solution 함수에서 return 해야 하는 값은 static으로 클래스에 선언하고
재귀, dfs를 사용하는 함수는 void로 선언해서, static result 값에 업데이트 하는 형식으로 했었는데
그런식으로는 구현할 수 있는 것들의 한계가 있다 보니, 좀 더 다양하게 접근할 수 있도록 하고자
타입을 return하는 함수를 작성했다.
현재 node의 next 주소를 backnumber에 재귀적으로 입력하는 방식으로,
입력된 node(이전에 호출된 node의 next)가 null 값이라면, linked list의 끝에 도달했다고 판단,
0을 return하고, 이제껏 쌓인 backnumber 함수들이 연속적으로 호출되면서
각 노드에 저장된 값 * length 파라미터의 10 제곱승을 return하는 방식으로 구현했다
(input이 [5,6,4] 였다면, 4*(10^2) + 6*(10^1) + 5*(10^0)을 return한다)
/**
이 함수로 submit 했을 때는 accpeted 되지 않았다. 삽질 과정에서 생긴 실수.
하지만 기본적인 recursion 방식의 뼈대는 제출해서 accpected 성공한 함수와 동일
**/
public int backnumber(ListNode lst, int length){
if(lst == null){
return 0;
}
return ((int)Math.pow(10, length) * lst.val) +
backnumber(lst.next, length + 1);
}backnumber 함수에서 return 된 값인, linked list에서 역순으로 숫자를 복구한 값 2개를 서로 더한 다음에,
String 배열에 담고자 형변환을 하고 , split("")을 해 주었다.
int test = backnumber(l1, 0) + backnumber(l2, 0);
String temp1 = Integer.toString(test);
String [] temp2 = temp1.split("");아마 이번 문제를 풀면서 가장 나를 절망하게 했던 recover 함수 구현은, 배열로 생성된 String 타입의 숫자들을
정수로 다시 변환하고 Linked List에 담는 것이었다.
우선 초기 node는, temp로 입력된 String 배열 중 첫 인자를 사용하여 생성하고,
배열의 나머지 값들은 while문을 돌면서
ListNode(int val, ListNode next) {this.val = val, this.next = next;} 생성자를 활용해서,
val에는 temp의 값을, next는 이전에 생성된 node를 지정하며, 연쇄적으로 감싸주는 방식을 활용했다
처음에는 이 과정도 재귀로 구현해야 하나 싶었으나, 제출 editor 상단에 주석 처리 된 ListNode 클래스를 한참이나
처다보면서, 두번째 생성자를 활용할 방법을 계속 고민했던 거 같다.
lst = new ListNode(Integer.parseInt(temp[length]), lst);
이것도 어찌 보면 재귀라 할 수 있지 않을까?
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; }
} public ListNode recover(String [] temp, ListNode lst){
int length = 0;
lst = new ListNode(Integer.parseInt(temp[length]));
length += 1;
while(length < temp.length) {
lst = new ListNode(Integer.parseInt(temp[length]), lst);
length += 1;
}
return lst;
}하지만 제출 결과는 wrong answer
어느 입력 데이터에서 잘못된 값이 나왔나 확인하니, 문제를 알 수 있었다.
자바의 int나 long은 담을 수 있는 정수의 크기가 한정되어 있는데,
입력으로 들어올 수 있는 linked list의 크기는 100까지 가능하므로, 10^100의 숫자까지 처리할 수 있는 자료형이
필요한 것이었다.
이 사실을 틀린 정답을 확인하고서야 알았는데 제한 조건을 제대로 읽었다면 미리 파악하고 해결할 수도 있었을 것이다.
BigInteger를 활용하여 더 큰 범위의 숫자도 제대로 처리하고자 했는데,
BigInteger는 생성 시 String을 입력 받는다고 한다.
따라서 backnumber 함수의 return을 String으로 바꾸는 작업을 실시했다.
/**
이 함수도 문제가 존재한다. 하지만 간단하게 고칠 수 있다. 그것은 바로......
**/
public String backnumber(ListNode lst){
if(lst == null){
return "";
}
return Integer.toString(lst.val) + backnumber(lst.next);단순히 node 안에 존재하는 정수를, String으로 형변환 한 후 차례대로 옆으로 더해주기만 하면 되므로,
return해서 호출 시, 현재 정수에서 10^(length)를 곱해주는 과정이 필요 없어졌다. 따라서 length 파라미터는 삭제한다.
그러나 문제는 계속되었는데, test case에서는 통과했으나(사실 처음 제출할 때부터 그랬다.....)
실제 submit 하고 난 다음 자꾸만 accept되지 않는 케이스들이 존재하는 것이었다
[2,4,9], [5,6,4,9]가 input으로 들어 왔을 때, 기댓값은 [7,0,4,0,1] 이었으나,
([2,4,9] -> 942;
[5,6,4,9] -> 9465;
9465 + 942 = 10407;
역순으로 저장하면 [70401])
[8,9,8,5]가 내가 계산한 결과였던것으로 보아, input의 linked list를 역순으로 바꾸는 과정에서 잘못된 듯 싶었다.
고민은 오래 걸렸지만 해결을 어이없게도 간단했는데,
int를 return 할 시에는 10^(length)를 이용해서 정수가 들어갈 자릿수를 정확하게 입력할 수 있었지만,
String으로 변환된 node 안의 정수를 더할 때는, 본디 역수의 형태로 더해지는 것이 아닌, linked list 에 담긴 순서대로
더해지는 것이었다.
/**
backnumber(lst.next)와, Integer.toString(lst.val)의 위치를 바꿔주면 되는 것이다
linked list의 끝에 도달하고, return을 하면서 차례대로 String으로 변환된 node 안의 값을 더해줄 때,
역순으로 더해질 수 있도록 보장해야 한다
**/
public String backnumber(ListNode lst){
if(lst == null){
return "";
}
return backnumber(lst.next)+ Integer.toString(lst.val);
}다섯번의 제출 끝에서야 Accpeted가 되었고 3시간 반 가량의 고민의 결과는
runtime은 순위권 밖이었고, 메모리 사용량은 하위 12. 32%였다.
삽질의 결과가 문제들만 겨우 풀 수준들이고 효율성까지 통과해야 하는 문제였다면 어떤 기분일지는 말도 못하겠다.
분명히 더 나은 방식의 풀이법이 존재한다는 뜻이니 더 열심히 공부해야겠다.
이번 LeetCode 문제를 풀면서 느낀 교훈은, 우선 제한사항을 잘 확인하자는 것이다.
입력으로 들어 올 linked list가 정수로 변환 되었을 때 int로는 담을 수 없다는 것을 파악 했더라면
더 빨리 좋은 해결을 할 수 있었을 것이다.
두번째는 재귀 함수에 대한 공부이다.
dfs bfs든, 백트래킹이든, 혹은 동적 계획법에서 응용해서 사용하든, 재귀가 코딩 시험 문제들의 절반을 차지하므로
재귀에 대한 더 정확한 이해와 응용이 필요할 것이다.
마지막으로, editor 상단에 제시된 기본 class 구조를 자세히 읽고 문제를 풀자는 것이다
두번째 생성자 함수를 잘 이용해서 recover 함수를 구현한 것처럼, 우선 문제에서 주어진 사항들을 최대한 자세히 읽고
이해한 다음에 설계 및 코딩을 하자
TMI) 코딩 스킬 체크는 프로그래머스에서만 주구장창 하다가, 백준도 딱 하나 풀어보긴 했는데
프로그래머스는 문제 수가 너무 적고,
백준은 input 처리하는게 상당히 귀찮고 test case마저도 없어서 고민이지만
LeetCode는 제출 시 어떤 input에서 틀렸는지 알려주기까지 한다.
(백준처럼 문제도 많고, 프로그래머스처럼 깔끔하게 class 내에서 solution 함수만 구현하고 답 return하기만 하면 되니까
사실상 두 코딩 테스트 사이트의 장점을 가지고 있다고 생각한다)
만약 제출 했을 때 어떤 case input에 에러가 났는지 알 수 없었다면(프로그래머스처럼)
한참을 더 고민하다 결국 이전처럼 좌절감과 함께 다른 사람의 풀이를 보게 되었을지도 모른다.
다른 사람의 풀이를 보는 것도 좋은 공부법이긴 하나, 이번 문제는 3시간 반을 넘게 고민하고
조금만 더 해보면 될거 같은데 라는 희망고문과의 싸움이었다.
아이디어는 있었고, 이를 구현하는 과정에서 뇌에 주름이 새겨지는 고통이었는데
블로그에 이렇게 자세하게 시행착오를 40분 가량 넘게 적는 거도
나름의 소소한 성취감 때문이고, 또한 앞으로는 어떻게 해야 겠다는 다짐을 위해서이다.
끝으로 코테를 풀면서, 언어 문법 때문에 버벅거리면서
구글링을 하면서 시간을 까먹는 경우가 실제 기업 지원 시에도 있었는데,
설계, 구현에만 집중해도 모자랄 판에, 기본적인 것들도 헤매서 아까운 시간 날리는 일은 없도록 해야 한다
그리고 이렇게 코테 풀이 과정 자세히 적는 것은 앞으로 하기 힘들거 같다. 너무 힘들어......;;;