Jay's Develop Note

문제 :

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

두개의 정렬된 연결 리스트가 주어지고, 이 두개의 연결리스트를 오름차순으로된 하나의 연결 리스트로 합쳐야 한다.

- 처음 든 생각 :

1. 첫번째 인자로 주어진 첫번째 연결 리스트의 head부터 시작한다. head의 .next는 head보다는 큰 값일 것이다(이미 정렬된 연결 리스트이므로). 그러면 첫번째 리스트의 .next를 확인하는것 보단, 두번째 인자로 주어진 두번째 연결 리스트의 head와 첫번째 head와 비교한다. 여기서 더 작은값을 결과 리스트에 추가한다(두개의 값이 같다면, 둘 다 추가해 준다. 위의 예시처럼, 두 연결 리스트의 head가 모두 1이라면, 결과 리스트에 두개의 '1' 노드를 더해준다.)  

2. 두번째 노드도 같은 로직을 적용시킨다. 각 연결 리스트의 2번째 노드인 '2', '3'을 각각 비교해 더 작은 값을 결과 리스트에 먼저 더해준다. 하지만 여기서 무턱대고 3을 2 다음에 넣으면 안 된다. 1번에서는 두 노드의 값이 같기 때문에 한번에 두 노드를 결과 리스트에 저장했다면, 이번에는 값이 다르기 때문에 두 노드를 다 넣으면 안된다. 예를 들어보자. 첫번째 연결 리스트(1->2->3)와  두번째(1->4->5)가 있을때, 위의 로직을 따르면 (1->1->2->4-> ... ) 이렇게 될 것이다. 그렇지만 첫번째 연결 리스트의 다음 값은 3이고, 3은 4보다 작으므로 (1->1->2->3->4) 가 되어야 한다. 즉, "노드의 값이 같을 때에만 결과 리스트에 동시에 노드를 넣어주고, 그렇지 않다면, 두 노드를 비교해 두 노드중 작은 값만 결과 리스트에 넣어준다." 이때, 이미 값을 넣은 연결 리스트의 head만 .next를 통해 업데이트를 해 주고, 들어가지 않은, 즉 이번 예시에서 두번째 노드는 .next를 하지 않고, 즉 '4' 노드를 또 다시 첫번째 연결 리스트의 다음 노드와 비교해 준다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
         dummy = ListNode()
         curr = dummy
        while list1 and list2:               
            if list1.val < list2.val:
                curr.next = list1
                list1, curr = list1.next, list1
            else:
                curr.next = list2
                list2, curr = list2.next, list2
                
        if list1 or list2:
            curr.next = list1 if list1 else list2
            
        return dummy.next

위의 코드를 살펴보자. 먼저, 

• dummy = ListNode()를 살펴보면, 먼저 더미 노드 하나를 만들어준다. 이 더미노드는 생성 당시 위에서 정의된 생성자로 인해 '0'이라는 값을 가진 하나의 노드가 생성된다.
• 이제, 이 노드를 추적할 수 있는 포인터 curr도 설정 해 준다.  여기서의 '추적' 이란 말은, 노드를 추가 해야할 때, 어디에 추가해야할지를 트래킹 하는 포인터이다.
• while list1 and list2 : list1과 list2의 노드들이 존재하는동안 반복한다.
• 만약, list1의 노드값이 list2의 노드값보다 작다면, 현재(curr)의 다음 노드를 list1로 설정해준다. 왜냐하면 현재 curr노드의 값은 0이므로, 0 다음에 제일 작은 수를 0의 다음값으로 설정 해 준다. 그리고, 이미 list1의 현재값은 추가되었으므로, list1.next를 통해 다음 while loop에서는 다음 노드 값을 비교 할 수 있도록 포인터를 업데이트 해 준다. 또한, curr에도 방금 추가된 노드가 있으므로(원래 curr은 더미 노드인 '0'을 가리키고 있었음), curr또한 업데이트 해 준다.
• 만약 list1의 노드값이 list2의 노드값보다 크다면(즉, 이 케이스에서는 list2의 노드값이 다음에 이어져야 한다),  현재 노드의 다음값으로 list2를 해 준다. 그 다음, 위에서 했던것과 같이 list2의 노드 포인터를 다음 노드로 업데이트 해 주고, 현재값을 방금 추가한 list2로 업데이트 해 준다.
• while문에서 두 연결 리스트의 모든 노드들을 비교하고 병합 작업을 마친 후, 마지막 if문을 살펴보자
• 먼저, 두 연결 리스트중 하나라도 노드가 남아있는 연결 리스트가 존재할 경우, 현재노드(여기서의 현재 노드는 합쳐진 연결 리스트의 맨 마지막 일것이다)의 next로 남아있는 리스트를 더해준다. 
• 결국 마지막엔 dummy.next를 리턴하면 처음에 만들었던 더미노드값 '0'뒤의 모든 값들을 리턴 할 것이다. 

※ 몰랐거나, 오랜만에 다시 기억난 내용들: 

- 나는 첫번째 while문에서 연결리스트의 끝까지 검사하는 조건을 while list1.val != None and list2.val != None으로 생각했다. 사실 이게 더 정확한(?) 코드이지만, 런타임이 더 느려질 것이다. 이유는 다음과 같다. 우리는 노드의 값이 무엇인지는 여기서 알 필요는 없다. 여기선 노드의 끝에 도달했는지 아닌지만 알면 되므로, 굳이 노드의 값이 None인지는 비교해 줄 필요가 없다. 만약, 내가 처음 생각한것 처럼 list1.val != None을 하게되면, 노드의 속성에 한번 더 불필요하게 접근하게 되므로(.val은 노드의 속성에 접근), 런타임이 늘어난다.

- 파이썬의 다중할당(Multiple Assignment) : list1, curr = list1.next, list1 부분을 살펴보면, 파이썬에서는 다중 할당을 할 수있다. 사실 문법 자체가 직관적이라 바로 이해할 수 있었지만, 까먹었다가 되찾은 내용이니 여기에 기록하겠다.

- if list1 or list2 : 여기서 list1과 list2는 노드를 참조하는 포인터일뿐, 연결 리스트 전체를 의미하는것은 아니다. 여기서는 list1 또는 list2중 하나라도 참이거나 아닐 경우를 판단하는 구문인데, 포인터의 참 / 거짓을 어떻게 확인 할 수 있을까? 파이썬에서는 'None(자바에서의 null)'은 거짓(False)로 평가되며, 여기서는 노드를 가리키고 있으면(즉, 남아있는 노드가 있으면) 참으로 판단된다.

- list1: Optional[ListNode]는 Python의 타입 힌트(Type Hinting)로, list1이 ListNode 객체이거나 None일 수 있음을 나타낸다. 이는 list1이 연결 리스트의 첫 번째 노드를 참조하는 포인터일 수 있고, 또는 빈 리스트를 나타내기 위해 None일 수도 있음을 의미한다. 즉, Optional 뒤의 square bracket안에는 None이외의 다른 타입을 명시 해 준다. 예를들어, var = Optional[String]이라면, var이라는 변수는 None타입을 가질수도 있고, String을 가질수도 있다는 의미이다(None, String이외의 타입은 올 수 없다). 정적 타입 검사 도구(mypy 등)를 사용하면 타입 불일치 오류를 사전에 감지할 수 있다. Python 자체는 동적 타이핑 언어이므로 타입 불일치로 인한 직접적인 런타임 오류를 발생시키지 않지만, 잘못된 타입을 처리하려고 할 때 AttributeError와 같은 오류가 발생할 수 있다.
타입 불일치가 발생하면 정적 타입 검사 도구에서 타입 불일치 오류(TypeError)가 보고된다.

- curr.next = list1 if list1 else list2 : 파이썬에서의 삼항 연산자이다. 이 삼항 연산식을 풀어쓰면 다음과 같다.

if list1 :

   curr.next = list1

else :

   curr.next = list2

문제 : Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

이번 문제는 파이썬으로 풀어 보겠다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root, depth):
            if not root: 
                return depth
            return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1))
        
        return dfs(root, 0)

먼저, 깊이우선탐색(dfs) helper 메서드를 만들어 재귀적으로 호출하려고 한다. 

- 만약 루트노드가 None이면, 즉 트리가 비어있으면 맨 처음 maxDepth 호출시 인자로 주어졌던 dfs의 두번째 인자 '0'을 리턴한다.

- 그게 아니라면(비어있는 트리가 아니라면), dfs(root, 0)이 호출되어 maxDepth의 인자로 주어진 root과 처음 depth 0을 인자로 가지고 함수가 호출된다. 위의 첫번째 예시를 들어보자.

- 루트는 '3'이다. 즉, 첫번째 if문에서 false가 반환되므로  return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1)) 가 재귀적으로 호출 될 것이다. 

- 이 재귀 호출문을 살펴보면 왼쪽 서브트리, 오른쪽 서브트리를 모두 깊이 우선탐색을 각각 진행 한 후, max를 사용해 최댓값(이 문제에서 구하고자 하는 최대깊이)를 리턴한다.

- 즉, 첫번째 예시의 경우엔 재귀문이 호출되면 왼쪽 서브트리의 루트 '3'에서 dfs가 호출 될 것이고, 여기서 또다시 재귀함수가 호출될 것이다(루트는 None이 아니라 '3'이므로). 그러면 또다시 3의 왼쪽, 오른쪽 서브트리에서 재귀문이 호출되는데, 여기서는 루트 '3'의 서브트리의 left, right모두가 None이므로 첫번째 if문에 걸려 depth == 2가 리턴될 것이다.

- 이번엔 오른쪽 서브트리를 살펴보면, 루트에서 재귀문이 호출되고(depth == 1), 또다시 루트가 '20'인 서브트리에서 재귀문이 호출되고(depth == 2), 또다시 루트가 각각 '15' '7'인 노드에서 재귀문이 호출된다(depth == 3). 이 두 노드의 자식 노드들은 비어있으므로 depth == 3이 리턴될 것이고, 우리가 찾고자하는 최대 깊이를 찾기 위해선 최상단 루트노드를 기준으로 왼쪽 서브트리, 오른쪽 서브트리의 깊이중 최댓값을 리턴하면 되므로 max를 사용해 최대 깊이를 리턴한다.

※ 헷갈렸던점

- if not root는 자바로 표현하면 if(root != null)과 같고, 또 if root != None : 과 같이 표현 할 수 있다.

- 처음에 빈 트리를 생각했을때, 맨 처음 if not root : return depth를 보고 헷갈렸다. ("아니 루트가 아예 없는 텅 빈 트리면 0을 리턴해야 하는데 도대체 depth = 0은 어디에 초기화 되어있지? depth = 0으로 초기화를 시키면 그냥 return depth 일텐데, 초기화도 되지 않은 depth를 어떻게 리턴한다는거지? 함수의 반환형은 int인데,,,

- main함수에서 호출하는건 maxDepth함수이다. maxDepth함수를 살펴보면 dfs다음에 바로 return dfs(root, 0)이다. 즉, maxDepth함수를 호출하면 dfs(root, 0)를 호출한다. 즉, 여기서 depth를 0으로 초기화 시키면 된다.

항상 파이썬에서는 indentation을 신경 써야 할것같다

문제 : 두 개의 비어있지 않은 연결 리스트가 주어집니다. 이 리스트들은 각각 하나의 비음수 정수를 나타내며, 각 노드는 한 자리 숫자를 포함하고 있습니다. 숫자는 역순으로 저장되어 있습니다. 두 숫자를 더한 후, 그 합을 연결 리스트로 반환하세요.

두 숫자는 숫자 0 자체를 제외하고는 앞에 0이 포함되어 있지 않다고 가정할 수 있습니다.

예시 :

즉, 두개의 연결 리스트가 주어지고, 그 연결 리스트를 처음  tail부터 head까지(역순) 연속된 노드들을 이어 정수를 만들고, 그 두 값을 더해 새로운 연결 리스트로 리턴 해야한다.

1. 처음 나의 생각 : 

일단 연결 리스트가 주어졌고, 위의 예시 첫번째를 보면 2 -> 4 -> 3이다. 이 연결 리스트를 뒤에서부터 읽으면 342이다. 자 그럼, 이 연결 리스트를 어떻게 342라는 정수로 표현 할 수 있을까?

342 = 300 + 40 + 2

즉, 초기 자릿수 값을 1로 설정하고, 노드를 넘어갈 때마다 그 자릿수에 10을 곱해 정수를 만든다. 예를 들어, head부터 읽으면 2가 읽힐것이다. 이때, 2와 초기 자릿수값 1을 곱해 sum1(첫번째 인자로 주어지는 연결리스트의 합)이라는 변수에 2를 더하고, 그 다음 노드로 넘어가면 4를 읽고, 이 4와 업데이트된 자릿수 값 10을 더해 40을 sum1에 더한다.(2 + 40 = 42) 마지막으로, 그 다음 노드의 값인 3을 읽어와 업데이트된 자릿수 값 100이랑 곱한다(300 + 40 + 2). 

두번째 연결리스트 인자도 같은 방식으로 총합을 계산 한 후, 총합이 1보다 클때까지 나머지 연산(modulo)를 이용해 각 자릿수의 값을 가져온다. 그 다음, 그 값을 다시 새로운 연결 리스트에 담아 반환한다.

코드는 아래와 같다.

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(0);
        ListNode rCurrent = dummy;

        ListNode current = l1; 
        ListNode current2 = l2; 

        int l1Sum = 0;
        int l2Sum = 0;
        int digit = 1;
        int digit2 = 1;

        while(current != null) {
            l1Sum += current.val * digit;
            current = current.next;
            digit *= 10;
        }

        while(current2 != null) {
            l2Sum += current2.val * digit2;
            current2 = current2.next;
            digit2 *= 10;
        }

        int total = l1Sum + l2Sum;

        if (total == 0) {
            return new ListNode(0);
        }

        while(total > 0) {
            int digits = total % 10;
            rCurrent.next = new ListNode(digits);
            rCurrent = rCurrent.next;
            total /= 10;
        }
        return dummy.next;
    }
}

일단 여기서 연결 리스트와 관련된 궁금증 몇가지를 풀고 가 보자. 

• dummy : 말 그대로 연결 리스트의 첫번째 값을 참조하기 위해 만든 임시 노드이다. 생성자에 0을 넘겨, 그냥 임시 노드(시작노드)를 만든 것이다. 이 dummy는 나중에 최종 연결 리스트를 반환할때 사용된다. 예를들어, 우리가 만약 1->2->3을 반환해야 한다면, dummy노드를 이용해 0->1->2->3 와 같은 연결 리스트를 만들고, 앞의 0을 제외한 나머지 1->2->3 을 반환해주면 된다.
• dummy.next : 왜 next를 반환할지부터 생각 해 보자. 맨 처음에 dummy 노드는 노드의 값을 0으로 초기화 해 주었다. 하지만 이 더미 노드는 말 그대로 노드의 시작점을 참조하기 위해 우리가 임의로 만든 것이고, 여기에 dummy.next를 하면 뒤의 값이 모두 반환된다. 연결 리스트의 특징 :. .next로 다음 노드를 참조하면, 다음 노드 뿐만 아니라 next로 연결되어있는 노드까지 모두 반환한다.

하지만... 기본적인 테스트 케이스 몇개를 제외하곤 너무나도 많은 테스트 케이스를 통과하지 못 했다. 문제를 보니,,, 테스트 케이스로 준 연결 리스트는 제일 긴 총 합이 899,999,999였다. 그런데 테스트 케이스는 int로 커버가 불가능한 long의 영역까지 커버해야하는것을 알고, 형 변환을 해 주었다. 하지만 이번에는 1884개의 테스트중 3개의 테스트가 또 다시 fail하였다. 문제를 보니 이건 int나 long의 문제가 아니였다. 내가 너무 단순한 수학적인 방식으로 풀려고 했기 때문에 실패했던 것이였다.

2. 두번째 생각 : 그럼 type문제를 아예 빼놓고, 이 문제를 어떻게 해결 할 수 있을까?

아이패드에 연결 리스트 그림을 그려놓고 보니, 그냥 각 자릿수의 노드들을 서로 더해 같은 자릿수에 넣어주면 되는 것이였다... 굳이 복잡하게 일일히 1, 10, 100을 곱해주면서까지 정수를 만들고, 그 정수들을 다시 더하고 나머지 연산을 하는 등 복잡한 로직은 전혀 필요하지 않았다.

예를들어, 2->4->3 && 5->6->4는 (2+5) (4+6) (3+4)를 각각 그에 맞는 자릿수에 넣어주면 됐다. 하지만 여기서 문제가 하나 생긴다. 가운데 4 +6 처럼 더한 값이 10이 넘어버리면 어떻게 해야 할까?(당연히 손으로 덧셈을 하면 어떻게 해야할지 안다. 하지만 이걸 코드로 어떻게 풀어낼까?) 

1. 'carry'라는 변수를 사용해 두 정수의 합이 10이 넘는지 안 넘는지 판단한다.

/**
 * 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; }
 * }
 */
class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode rCurrent = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            carry = sum / 10;
            rCurrent.next = new ListNode(sum % 10);
            rCurrent = rCurrent.next;
        }

        return dummy.next;
    }
}

위의 코드를 보면 내가 처음 생각했던 코드보다 훨씬 간결하고 가독성이 좋다.

• 먼저, 처음과 같이 dummy를 0으로 초기화해 임시 노드를 만들고, current를 더미를 가리키도록 한다. 그 다음 내가 언급했던 carry(올림수)를 0으로 초기화 한다.
• int sum = carry : 이전 계산에서 두 정수의 합이 10이 넘었는지 확인하고, 넘었다면 다음 덧셈값에 이 carry(올린 자릿수)를 추가로 더해준다. 예를들어, 예를 들어보자.
  
  • 첫번째 while loop : sum은 0으로 초기화 되어있다. 이 sum에다가 각 연결 리스트의 head값인 2  + 5를 해 준다. 그럼 7이고, 7은 10을 넘지 않으므로 carry의 값은 7 / 10으로 0.7이지만, 자바에서의 int는 정수 뒤의 소수점을 무시하므로 첫번째 while에서는 carry의 값이 0이 된다. 그 다음, dummy node의 다음 노드값으로 결과값을 넣어준다. 7 % 10은 7 임으로 현재 결과노드는 이렇게 생겼다. 0 -> 7.
  • 두번째 while loop : sum은 다시 0으로 초기화 된다. 첫번째 while loop에서 10을 넘지 않았기 때문이다(== carry가 0임.). 이제 노드의 두번째 값들을 서로 더해준다. (4 + 6) 그러면 sum은 10이 되지만, carry 10/10에서 carry는 1이 된다. 여기서 1은 이제 다음 sum에서 올려줘야 할 값이다. 그 다음 10 % 10 = 0를 결과 노드에 다음 노드로 추가 해 준다.
  • 세번째 while loop : sum은 0이 아니라 1로 초기화 된다(이전 while loop에서 올림값). 이제 각 연결 리스트의 마지막 값들을 더해준다. (4+3) 하지만 여기에다가 우리가 10이 넘어 올라온 올림값 1을 더해 8로 만들어 준다. 이제 이 8을 마지막 결과 노드로 넣어주면 우리가 원하는 값을 얻을 수 있다.

이렇게 문제를 풀고 나니 느낀점 :  처음부터 코드를 다짜고짜 써 내려 갈 생각을 하지 말고, 문제를 좀 더 꼼꼼히 보고 종이와 펜을 준비해 어떠한 다른 방법이 있는지부터 천천히 살펴보자.