LeetCode 2번 Add Two Numbers를 풀어보자..

지난번 1번 문제는 easy이기도 했고, 첫 문제이다 보니 확실히 쉬웠다. 

2번 문제는 medium에 통과율도 30%정도이니 긴장을 하며 문제를 확인하였는데..

일단, 2번 문제는 링크드 리스트, 즉 연결 리스트를 사용할 줄 안다면 쉽게 해결할 수 있는 문제로 보인다.


문제는 다음과 같다.

비어 있지 않은, 두 개의 양수 연결 리스트를 제공한다. 두 개의 리스트에는 각각 거꾸로 한 자리의 숫자씩 들어가 있다.

두 개의 리스트를 읽어서 합을 한 후, 한 자리씩 거꾸로 연결 리스트에 넣은 후에 반환하면 된다.

 

예를 들면 아래와 같다.

입력 값 : list1 = [2, 5, 1], list2 = [1, 3, 5]

출력 값 : list = [3, 8, 6]

주의할 점은 세 가지 정도로 생각한다.

- 두 정수의 합으로 인해 자릿수가 변경되는 경우.

두 정수의 합으로 인한 carry가 발생한다면, 역시 표시를 해야 한다는 것이다. 즉, 653 + 351 = 1004 인데, 출력 리스트에는 [4, 0, 0, 1]을 만들어서 반환 해야 한다는 것이다.

- 두 리스트의 자릿 수가 다른 경우.

코딩할 때, 같은 리스트가 나오지 않을 수도 있다. 그러므로, 시간 줄이겠다고 하나의 리스트 사이즈만 읽다가 실수 하기 보다는, 각각 리스트를 순차적으로 읽고 값을 만드는게 중요하다고 생각한다.

- 연결 리스트 사용하는 방법.

사실, 이게 가장 중요하다. 연결 리스트에 대해 사용법을 모를 수도 있다. 이 경우에는 프로그래밍 책을 먼저 읽어보는게 중요하지 않을까 싶다..


그래서 일단 문제는 아래처럼 풀었다.

  1. 각 연결 리스트가 존재하는지 또는 두 개의 값이 새로운 자릿수를 만들었다면 loop를 돈다.
  2. 각 연결 리스트가 존재한다면, 현재 노드에 값을 가져오고 다음 노드를 가리킨다.
  3. 두 값과 이전 노드에서 발생한 carry값을 더하여, 10의 나머지를 sum으로 저장하고, carry가 발생하였다면 값을 저장한다.
  4. 새로운 연결 리스트에 해당 값을 입력하고, 1번 과정으로 돌아간다.


위에서 말했지만, 문제는 어려운 편이 아니다. 다만, 연결 리스트를 모른다면 충분히 헤멜 수 있는 문제라 생각한다.


아래는 문제를 풀면서 예제에 대해 정리해놓은 것인데 참고하면 좋을 것 같다.

list1 = [1, 2, 3]

list2 = [9, 4, 7, 1, 9, 9, 9, 9, 9, 9, 9]


list1 = [0]

list2 = [0]


list1 = [1, 2, 3]

list2 = [3, 4, 7]


list1 = [4, 5, 7, 1]

list2 = [6, 4]

 

list1 = [3, 7, 2]

list2 = [1, 3, 8, 1, 9]

 

이정도 예제를 통과한다면 submit 해도 괜찮지 않을까 싶다.


아래는 통과 기준으로 런타임 분포도인데, 이번엔 중간쯤 나오지 않았나 싶다..

이런 자료 보이면 상위권으로 가고 싶은게 사람 마음이라..

댓글