LeetCode[Java] - Add Two Numbers 풀이

안녕하세요 Ruk 입니다. 오늘은 LeetCode의 Add Two Numbers 문제를 풀어본 내용을 공유하려 해요.

 

2개의 ListNode가 주어졌을 때 10진법의 숫자 합산 연산을 하여 ListNode를 다시 반환하는 문제내요.

예시를 보면 각 노드의 첫번째 자리는 1의 자리로 정의가 되어있습니다.

 

해결 방법으로는 아래와 같이 정리하습니다. ( 개인적으로 알고리즘을 풀 때 해당 문제에서 처리해야할 요건을 정리 후 풀이에 들어가는게 코드 짜기에 전 더 편하더라고요. )

 

1. 각 노드가 null인지 확인 후 합산한다.

2. 2개의 노드중 하나라도 next노드가 존재하면 반복한다.

3. 10이 넘어가면 carry를 체크한다.

4. 2개의 노드가 null이더라도 carry가 존재하면 자리수 1을 올려준다.

위 4가지 조건을 순차대로 구현을 해보았더니 모든 케이스에 통과가 가능했습니다.

속도 또한 무난하게 돌아간것 같은데 메모리가 좀 높게 사용되는 듯 싶내요.

 

해서 조금 더 생각을 해 보았더니 메모리를 최적화 시키는 방법이 떠올랐습니다.

 

- ListNode result = new ListNode(0); 로 노드를 생성하여 result값을 저장하는 방식이 아니라

input params로 주어진 ListNode l1을 사용한다면 조금 더 줄일 수 있을 것 같내요.

다만 그렇게 짜게된다면 boolean값을 통하여 null상태가 된 적이 있는지 별도로 관리를 해야하기에

지금 코드에 만족하며 끝내었습니다.

 

해당 코드의 속도와 메모리는 아래와 같이 나오게 되었습니다.

과거에도 1번 풀었던 기록은 있었지만, 이번에 풀 때 보다 빠르고 메모리도 최적화 된 것 같아 기분이 좋내요.

 

새로운 의견은 댓글로 주시면 참고하여 학습하도록 하겠습니다.