[Python] Leetcode 2. Add Two Numbers

문제

각 노드의 값이 0~9 사이인 Linked List 두 개가 주어진다. 리스트 안의 값들은 역순으로 저장이 되어 있다. 두 리스트 속의 노드의 합을 새로운 Linked List에 저장하면 된다. 역순으로 저장이 되어있기 때문에 받아올림이 발생할 경우 뒤에 오는 값에 올려준다.

예시

예시를 보면, 각 Linked List의 중간에 있는 노드 값의 합은 10이다. 하지만, 각 노드의 값은 0~9 사이로 올 수 있으므로, Next에 오는 노드에 받아올림이 전달되고, 3+4+1의 값으로 8이 오는 것을 볼 수 있다.

입출력

Input1: l1 = [2,4,3], l2 = [5,6,4]
Output1: [7,0,8]

Input2: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output2: [8,9,9,9,0,0,0,1]

내 풀이

• Linked List에 대한 이해만 있다면 어렵지 않게 풀 수 있는 문제라고 생각한다.

• 내 경우에는 리스트 안에서 노드를 이동시키면서 각 노드의 값을 더해 출력할 List에 저장해줬는데, 이 방식으로 풀 때 주의할 점은 Root Node의 값을 저장하지 않으면 찾을 방법이 없다는 것이다. 맨 윗줄의 ListNode 클래스는 문제에서 주어졌는데, Double Linked List가 아니기 때문에 현재 노드를 Next로 갖고 있는 Node를 찾기 어렵기 때문이다.

• 내 경우에는 While Loop가 돌아가기 전에 result에 temp Instance를 지정해서 Root Node를 확보한 이후 L1,L2 노드의 값을 찾아 순서대로 더했다.

코드

후기

• Leetcode를 처음 이용해봤는데, 문제를 푼 시간과 사용한 메모리의 양을 다른 사람들과 비교해서 보여주는 것이 효과적이었다. 처음 작성한 코드에서는 다른 사람들에 비해 시간을 많이 소모한 것을 발견했고, 한번 다듬은 코드가 위 코드이다.
• 그럼에도 불구하고 더 효율적인 방법이 많이 있었다. 한 가지 떠오르는 대안은 역순으로 되어 있는 L1과 L2의 값을 다시 역순으로 돌려 원래 순서로 만든 다음 덧셈을 하고 다시 거꾸로 결과 리스트에 집어넣는 방식이다. 정확하게 어느 쪽이 연산 속도가 빠른지 잘 모르겠다.(해보고 글을 수정하겠다.)

출처 및 링크

문제
https://leetcode.com/problems/add-two-numbers/
코드
https://github.com/ko-inseoklee/ProblemSolving/blob/main/2.AddTwoNumbers.py

풀이와 후기 이외에 다른 알고리즘이 있거나, 코드에서 불필요한 부분이나 더 효율적으로 사용할 수 있는 부분이 있다면 말씀해주세요.