[leetcode] Add Two Numbers (swift)

문제 

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

문제 요약

2개의 숫자를 더하는 간단한 문제입니다. 자료구조는 연결리스트를 사용합니다. 

아래 그림과 같이 A: 243, B: 564 라고 한다면 A + B 는 708이 됩니다.

 

풀이 

연결리스트 자료구조만 이해하고 덧셈에서 carry를 까먹지 않고 더합니다. 두개의 연결리스트를 계속 순회하면서, 새로운 연결리스트를 할당합니다.

풀이코드 1

연결리스트의 머리부분을 담당하는 startNode와 연결리스트를 순회하기 위해 필요한 curNode를 선언했습니다. (curNode는 연결리스트 자료구조의 tail부분의 역할이기도 합니다.) 그리고 addVal은 carry 역할을 합니다.

 

l1과 l2의 next가 없을 때까지 순회하면서 숫자를 더합니다. l1과 l2의 연결리스트의 개수가 달라 한가지 연결리스트는 모두 순회하지 않는 경우가 나올 가능성이 있기 때문에 l1과 l2 각각 마지막까지 조회했는지 체크합니다. 

 

마지막으로 carry가 1이 남을 경우 노드를 하나 더 추가해주어야 하기 때문에 해당 케이스도 고려합니다. 

런타임시간은 50ms로 최적화시킨 코드는 아닙니다. 그래서 절반만큼의 시간을 사용한 코드를 살펴보았습니다. 시간복잡도는 비슷하지만 코드의 길이가 절반 이하는 감소합니다. 코드의 길이를 줄이면서 메모리 사용량도 줄일 수 있을 뿐만 아니라 메모리 상에서 코드를 찾아가는 과정인 런타임시간도 줄일 수 있다는 사실을 확인할 수 있습니다!

 

풀이 코드 2