[Day2] 617. Merge Two Binary Trees/ 888. Fair Candy Swap (LeetCode)

617. Merge Two Binary Trees Easy

오늘 풀어볼 첫번째 문제는 LeetCode의 617. Merge Two Binary Trees 문제다.

문제를 요약하면 두 개의 이진트리가 있는데, 이 두 트리를 합쳤을 때 리턴되는 이진트리를 찾아내는 것이다.

여기서 규칙은 두 트리를 합칠 때 같은 위치에 이미 노드가 존재한다면 두 노드값의 합을 해당 위치에 넣어야한다는 것이다.

흠....... 우선 자료구조는... 문제에서 준 트리 구조를 써야지 (LeetCode의 이 문제는 친절하게도 주석으로 TreeNode라는 public Class의 구조를 알려준다.)

 

각 트리를 이렇게 (한 부모 두 자식)으로 묶어 생각하기로 했다.(이하 '작은 트리') 두 자식은 각각 다른 '작은 트리'의  root가 될 수 있다.

그리고 이때 root들은 해당 위치에 있는 값의 합을 자기의 값으로 갖고, 만약 merge될 상대트리의 자기와 같은 위치가 비었다면 자기 자신을 반환하면 될 것이다. 자기(루트)가 없다면 그 노드의 자식들은 당연히 없을테니 자신의 전체를 반환하면됨.

그리고 이 '작은 트리'들에 대한 뿌리합 연산을 Recursion으로 호출해서 뿌리의 두 자식 위치에 하위 뿌리를 달고 그 자식에 하위의 하위뿌리를 다는 식으로 생각하면 아래와 같은 Solution을 얻을 수 있다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        
        if (t1==null) {
            return t2;
        } else if (t2==null) {
            return t1;
        }
        TreeNode tNew = new TreeNode(t1.val+t2.val);


        if (t1.left != null) {
            tNew.left = t1.left;
            if (t2.left != null) {
                tNew.left = mergeTrees(t1.left, t2.left);
            }
        } else if (t2.left != null) {
            tNew.left = t2.left;
        }


        if (t1.right != null) {
            tNew.right = t1.right;
            if (t2.right != null) {
                tNew.right = mergeTrees(t1.right, t2.right);
            }
        } else if (t2.right != null) {
            tNew.right = t2.right;
        }

        return tNew;
    }
}

Solution의 메인 함수는 결과적으로 모든 트리를 아우를 수 있는 루트 노드하나를 return할 것이어서, 재귀 호출을 끝내기 위해서는 이 루트노드가 null일 때를 처리해줘야 한다. 합쳐야할 두 '작은 트리'의 루트 중 하나라도 null일 경우, 상대 루트 노드를 반환하면서 재귀 호출이 끝난다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
     
        if (t1==null) {
            return t2;
        } else if (t2==null) {
            return t1;
        }
        
        TreeNode tNew = new TreeNode(t1.val+t2.val);
        tNew.left = mergeTrees(t1.left, t2.left);
        tNew.right = mergeTrees(t1.right, t2.right);
       
        return tNew;
    }
}

첫번째 Solution도 Accepted 되긴했지만 if 문에서 같은 조건을 처리하기 때문에 코드를 refactoring한 최종 Solution 코드는 위와 같다.

Accepted

6 ms

41.4 MB

java

---

888. Fair Candy Swap Easy

Easy 문제를 해결한 덕에 오늘은 2문제 풀이가 가능! ><

두번째로 풀어본 문제는 역시 LeetCode사이트의 888. Fair Candy Swap 문제이다.

문제를 요약하면> Alice와 Bob이 있다.

둘은 서로 다른 종류의 캔디바를 각각 다른 갯수만큼 갖고 있다. 그리고 각 캔디바들의 길이는 모두 다르다.

배열 2개를 입력할 건데, A[i], B[j]이며 A의 사이즈는 Alice가 갖고 있는 캔디바의 갯수이고 A[i]는 Alice가 갖고 있는 i번째 캔디바의 길이를 뜻한다. B[j]는 Bob이 갖고 있는 캔디바에 대한 것.

그리고 그 와중에 두사람 모두 두 종류의 캔디바를 다 맛보고 싶다. 그래서 각자의 캔디바를 몇개씩 교환하기로 했다.

둘은 완전 베프라 자기가 손해를 보든 득을 보든 1도 신경쓰지 않고, 두사람이 최종적으로 같은 <길이>의 캔디바를 먹기를 원한다. (더 많이 갖고 있는 사람이 손해겠지만, 이건 신경안쓴다는 소리~)

그럼 이때, Alice의 몇번째 캔디바와, Bob의 몇번째 캔디바를 교환해야 둘이 같은 길이의 캔디바를 먹을 수 있을까???????

문제를 보고 방정식을 세워야겠다고 생각했다.

두 사람이 최종적으로 가져야하는 캔디바의 길이는 같아야한다. 그러므로 두사람이 갖고있는 모든 캔디바의 길이를 더해 반으로 나누면 이 길이가 각 두사람이 마지막에 가져야하는 캔디바의 길이가 된다.

(sumA + sumB) / 2 (sumA는 A배열 모든 원소의 합:Alice가 갖는 전체 캔디바들의 길이합, sumB는 bob이 갖는 모든 캔디바 길이의 합.)

그리고 동시에 앨리스와 밥이 마지막에 갖는 캔디바의 길이는 

Alice : sumA - lossA + lossB

Bob: sumB - lossB + lossA

이기도 하다. (lossA와 lossB는 각각 Alice와 Bob이 잃은 캔디바 길이, 즉 서로 교환한 캔디바의 길이이다.)

따라서 최종 방정식은 (sumA+sumB)/2 = sumA-lossA+lossB = sumB-lossB+lossA가 되고, 이를 간단히 하면

lossB = (sumB-sumA+2lossA)/2 가 된다.

import java.util.Hashtable;
class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumMore=0;
        int sumLess=0;        
        int[] ans = new int[2];
        int[] more;
        int[] less;
    
        if(A.length>B.length) {
            more = A;
            less = B;
        } else {
            more = B;
            less = A;
        }
        
        for (int i=0; i<more.length; i++) {
            sumMore += more[i];
        }
        
        for (int j=0; j<less.length; j++) {
            sumLess += less[j];
        }


        Hashtable<Integer,Integer> table = new Hashtable<Integer,Integer>();
        
        for (int i=0; i<more.length;i++) {
            table.put(sumLess/2-sumMore/2+more[i],more[i]);
        }
        
        for (int i=0; i<less.length;i++) {
            if (table.get(less[i]) != null) {
                if (A==less) {
                    ans[0] = less[i];
                    ans[1] = table.get(less[i]);
                } else {
                    ans[0] = table.get(less[i]);
                    ans[1] = less[i];
                }
            break;
            }
        }
     
        return ans;
    }
}

자 그럼 이 일차방정식을 어떻게 알고리즘으로 풀었느냐? >>>>>>>>> 해시테이블(Hashtable)이다.

우선 두 Integer를 키와 값으로 받는 Hashtable을 하나 정의한다. 

한 key와 value의 쌍이 방정식의 해가 된다.

lossA에 A배열의 원소들을 하나하나 집어넣으면서 lossB가 될 수 있는 값을 계산해 Hashtable에 넣는다.

그렇게 완성된 Hashtable에서 lossB에 해당되는 값을 하나하나 꺼내며 실제 배열B의 원소들과 비교해본다.

lossA일 때 lossB여야하는 그 값이 배열 B에 있으면??? 그 Pair가 바로 해답이 된다.

(위에서 more, less를 결정하고 이 more, less로 코딩한 이유는 최종 결과를 [A,B] 형식의 배열로 출력하기 때문에 항상 A가 앞에 오도록 하는 장치라고 생각하면 된다. )

Accepted

21 ms

42.5 MB

java

 이 문제를 통해서 Hashtable 개념을 복습했고, 일차방정식 푸는 문제에 대해 이 알고리즘을 이용할 수 있다는 사실도 배웠다.