Problem


Linked List 의 root 가 주어지면 뒤집은 Linked List 의 root 를 구하는 문제입니다.



Solution

문제를 푸는 방법은 총 두가지가 있습니다.

재귀와 반복입니다.

처음에 생각할 수 있는 건 재귀인데 Linked List 의 꼬리까지 쭉 들어간 다음에 node.next 를 변경 하면서 다시 돌아오면 됩니다.

예제를 통해서 어떻게 바뀌는지 알아보겠습니다.


1. 초기 상태

리스트를 끝까지 들어가면 4 부터 시작하게 됩니다 (5 는 head.next == null 이라서 빠져나옴)


2. head.next.next = head;

head.next.nexthead 를 가리키게 만들어서 4 와 5 는 서로를 가리키게 됩니다.


3. head.next = null;

head.next 를 null 로 만들면서 가리키는 게 없도록 만듭니다.

여기서 헷갈리는 점이 생길 수 있는데 head.next 를 null 로 만드는건 5 노드를 없애는 게 아닙니다.

말 그대로 4 가 가리키는 노드를 없애는 것이고 5 노드는 여전히 존재하고 주소값도 존재합니다.


4. 첫 번째 함수를 빠져나올 때의 최종 모습


5. 두 번째 함수는 다음과 같은 상태입니다.

4 노드가 가리키는 노드가 없기 때문에 NULL 노드를 가리킨다고 할 수 있습니다.


6. 두 번째 함수를 빠져나올 때의 최종 모습

여기까지 진행하면 3 -> 4 -> 55 -> 4 -> 3 으로 바뀐 사실을 알 수 있습니다.

이대로 처음 시작했던 루트 노드까지 반복하면 최종적으로 뒤집어진 Linked List 를 구할 수 있습니다.



Java Code

// 1. Recursive
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode result = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return result;
    }
}

// 2. iterative
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode parent = null;

        while (head != null) {
            ListNode current = head;
            head = head.next;
            current.next = parent;
            parent = current;
        }

        return parent;
    }
}

Kotlin Code

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        return head?.next?.let {
            reverseList(it).apply {
                head.next.next = head;
                head.next = null;
            }
        } ?: head
    }
}

Problem

 

난이도 Easy 문제입니다.

 

배열이 주어졌을 때 한 숫자를 제외한 나머지는 모두 한 쌍으로 존재합니다.

 

중복되지 않는 숫자를 찾아서 리턴하는 문제입니다.

 

단, 추가 조건에 추가적인 메모리 사용 없이 O(n) 에 풀어보라고 나와있습니다.



Solution

O(n) 에 푸는건 쉽게 할 수 있습니다.

 

Map, Set, Array 등을 활용하여 중복된 숫자를 체크하면서 for 문 한번만 돌면 됩니다.

 

변수 하나로 풀려면 문제의 조건을 잘 봐야 합니다.

 

중복된 숫자는 무조건 한쌍입니다.

 

그리고 비트 연산자 중에 XOR 연산이라는 게 있습니다.

 

XOR 은 두 비트가 같으면 0 다르면 1 을 리턴해줍니다.

 

그리고 이 XOR 에는 같은 숫자에 대해 XOR 연산을 두번하면 자기 자신이 된다는 특징이 있습니다.

 

위에 강조한 두 가지를 이용하여 쉽게 풀 수 있습니다.



Java Code 1

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;

        for (int num : nums) {
            result ^= num;
        }

        return result;
    }
}

 

Java Code 2

// without using extra memory
class Solution {
    public int singleNumber(int[] nums) {
        for (int i=1; i<nums.length; i++) {
            nums[0] ^= nums[i];
        }

        return nums[0];
    }
}

 

Kotlin Code

class Solution {
    fun singleNumber(nums: IntArray) = nums.reduce { acc, i -> acc.xor(i) }
}

Problem


난이도는 Easy 입니다.


이진 트리가 주어지면 가장 큰 depth, 즉 트리의 height 를 구하는 문제입니다.



Solution

재귀로 간단하게 구할 수 있습니다.


root 에서 0 으로 시작하여 depth 를 계속 끌고 내려가면서 max 값을 구하면 됩니다.


node 가 null 이 되는 leaf node 에서는 depth 를 반환하기 때문에 가장 큰 depth 값을 구할 수 있습니다.



Java Code

class Solution {
    public int maxDepth(TreeNode root) {
        return goDepth(root, 0);
    }
    
    public int goDepth(TreeNode node, int depth) {
        if (node == null) return depth;
        
        return Math.max(goDepth(node.left, depth + 1), goDepth(node.right, depth + 1));
    }
}


Kotlin Code

class Solution {
    fun maxDepth(root: TreeNode?): Int {
        return goDepth(root, 0)
    }
    
    fun goDepth(node: TreeNode?, depth: Int): Int {
        node ?: return depth
        
        return maxOf(goDepth(node.left, depth + 1), goDepth(node.right, depth + 1))
    }
}


Problem


Medium 문제입니다. (체감 난이도는 Easy)


두 리스트를 받아서 더하기만 하면 되는 문제입니다.



Solution 1

각 노드에는 음수가 아닌 한 자리의 정수가 있으며 각 자리의 숫자가 거꾸로 되어 있습니다.


따라서 l1, l2 를 순서대로 비교하면서 더해주고 10 이상인 경우 carry 를 다음 노드로 넘기면 됩니다.


l1, l2 의 길이가 다를 수 있기 때문에 null 체크만 잘 해주면 쉽게 풀 수 있는 문제입니다.



Java Code 1

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode result = node;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int sum = carry;
            
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            if (sum >= 10) {
                node.next = new ListNode(sum - 10);
                carry = 1;
            } else {
                node.next = new ListNode(sum);
                carry = 0;
            }
            
            node = node.next;
        }
        
        if (carry == 1) {
            node.next = new ListNode(1);
        }
        
        return result.next;
    }
}



Solution 2

Discuss 를 보니 굳이 carry 를 쓰지 않고 sum 변수 하나만을 사용하며 % / 연산으로 풀이할 수도 있었습니다.


% 연산 비용이 부담되지 않는다면 훨씬 깔끔한 것 같습니다.



Java Code 2

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode result = node;
        int sum = 0;
        
        while (l1 != null || l2 != null || sum > 0) {
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            node.next = new ListNode(sum % 10);
            sum /= 10;
            
            node = node.next;
        }
        
        return result.next;
    }
}


Problem


Easy 문제입니다. (체감 난이도는 Medium 입니다)


이진 트리가 주어지고, root 부터 아래로 내려가면서 연속된 노드들의 합이 sum 이 되는 경우의 수를 구하는 문제입니다.



Solution 1

반드시 연속되야만 하기 때문에 연속되지 않은 값은 갖고 있을 필요가 없습니다.


예를 들면 root 가 10 이고 left 자식인 5 를 탐색해야 합니다.


5는 현재 자신의 값과 root 와의 합인 [5, 15] 와 sum 을 비교해야 합니다.


이걸 List 를 넘기는 대신에 10 을 더하는 경우, 더하지 않는 경우 두가지로 나누어서 호출하면 됩니다.



Java Code 1

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        
        return pathSequenceSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    public int pathSequenceSum(TreeNode node, int sum) {
        if (node == null) return 0;
        
        int count = (sum == node.val) ? 1 : 0;
        count += pathSequenceSum(node.left, sum - node.val) + pathSequenceSum(node.right, sum - node.val);
        
        return count;   
    }
}



Solution 2

Discuss 에서는 HashMap 을 사용하여 O(n) 에 푸는 풀이가 있었습니다.


처음에는 이해를 잘 못했지만 차근차근 로그를 찍어가면서 확인해보니 어느정도 알 것 같았습니다.


HashMap 에다가 지금까지 지나온 노드들의 누적 합을 저장해두고 있는지 확인하면 됩니다.


예제를 보고 설명해보겠습니다. 위 Example 중에서 [10, 5, 3, 3] 만 본다고 생각합시다.


가장 끝의 자식노드인 3 에서 확인해야될 값은 [현재 노드의 값, 부모 노드부터 누적합, 조부모 노드부터 누적합... root 노드부터 현재까지 누적합]


이렇게 트리의 높이에 비례하여 비교해야될 값이 늘어나서 첫 풀이에는 List 를 넘겼었습니다.


이번에는 루트노드부터의 누적합을 HashMap 에 저장해두면 됩니다.


HashMap 은 { "누적합" : "갯수" } 형식으로 예제를 기준으로 {10 : 1, 15: 1, 18: 1, 21: 1} 이렇게 [10, 15, 18, 21] 이 한개씩 들어가있습니다.


그리고 누적합에서 target 넘버를 뺀 값이 map 에 존재한다면 현재 노드부터 루트 노드까지 연속된 노드들의 합 중에 일치하는 값이 있다는 뜻입니다.


마지막 노드인 3 에서 가능한 sum 의 경우는 [21, 11, 6, 3] 입니다.


현재 노드까지의 누적합 21 에서 [21, 11, 6, 3] 을 빼면 [0, 10, 15, 18] 입니다.


HashMap 에 들어있는 값과 똑같지 않나요?


마지막 노드까지 나올 수 있는 연속합들을 한번에 비교할 수 있습니다.


근데 map 에 0은 없는데 어디서 넣을까요?


root 부터 현재 노드까지 더한 경우가 sum 이 될 수도 있기 때문에 처음에 {0: 1} 을 넣고 시작합니다.


그림 없이 설명하려니 좀 힘들 수가 있는데 코드를 보면 더 이해하기 쉬울 수도 있습니다.



Java Code 2

class Solution {
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return recursive(root, 0, sum, map);
    }
    
    public int recursive(TreeNode node, int accumulateSum, int sum, HashMap<Integer, Integer> map) {
        if (node == null) return 0;
        
        accumulateSum += node.val;
        int count = map.getOrDefault(accumulateSum - sum, 0);
        
        map.put(accumulateSum, map.getOrDefault(accumulateSum, 0) + 1);
        count += recursive(node.left, accumulateSum, sum, map) + recursive(node.right, accumulateSum, sum, map);
        map.put(accumulateSum, map.get(accumulateSum) - 1);
        
        return count;
    }
}


Problem


Medium 문제입니다.


candidates 에 있는 원소들 중 합이 target 이 되는 리스트 묶음을 return 하면 됩니다.



Solution

원소들은 중복해서 사용될 수 있지만 결과에는 중복되는 list 가 없어야 합니다.


처음에는 DP 로 생각했으나 우리가 구해야되는건 List 들의 목록입니다.


각 단계별로 저장되는 값은 List 이고 결국 메모이제이션을 통해서 다음 값을 구하려고 해도 저장된 List 만큼 전부 순회해야 합니다.


결국 백트래킹과 큰 차이가 없기 때문에 정해는 백트래킹이라고 생각합니다.


현재 candidate 값이 target 보다 작으면 temp 리스트에 넣은 뒤 다음 target 을 target - candidate 하여 계속 호출해줍니다.


만약 target 값이 0 이 된다면 temp 에 있는 값들의 합이 target 이라는 뜻이므로 result 리스트에 넣어주면서 쭉 돌면 됩니다.


candidates[0] 부터 시작하며 candidates[1] 부터 시작할 때는 이전값인 candidates[0] 값을 볼 필요가 없으므로 백트래킹 함수에 index 를 같이 넘깁니다.



Java Code

class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        for (int i = 0, len = candidates.length; i < len; i++) {
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(candidates[i]);
            backtracking(candidates, i, 1, target - candidates[i], temp);
        }
        
        return result;
    }
    
    public void backtracking(int[] candidates, int index, int tempSize, int target, List<Integer> temp) {
        if (target == 0) {
            result.add(new ArrayList(temp));
            return;
        }
        
        for (int i = index, len = candidates.length; i < len; i++) {
            if (candidates[i] <= target) {
                temp.add(candidates[i]);
                backtracking(candidates, i, tempSize + 1, target - candidates[i], temp);
                temp.remove(tempSize);
            }
        }
    }
}


Problem


Medium 난이도의 문제입니다.


nums 배열에서 합이 0이 되는 세개의 원소 리스트들을 return 하면 됩니다.



Solution

백준에 있는 세 용액과 비슷한 문제이지만 해당되는 리스트를 전부 return 해야된다는 점과


배열에는 중복된 원소가 존재하지만 실제 return 하는 값에는 중복된 리스트를 전부 빼야 한다는 점이 다르다고 할 수 있습니다.


세 용액을 풀었던 것과 마찬가지로 모든 원소들에 대하여 두 용액 풀이로 리스트를 구했습니다.


두 용액 풀이 (a + b = c 가 되는 ab 구하기)

  1. 배열을 오름차순으로 정렬합니다.
  2. 배열의 양 끝에 있는 숫자의 합과 c 를 비교합니다.
  3. 합이 c 보다 작다면 왼쪽 index 를 1 증가 시킵니다. (c 보다 작기 때문에 작은 값을 증가시킴)
  4. 합이 c 보다 크다면 오른쪽 index 를 1 감소 시킵니다. (c 보다 크기 때문에 큰 값을 감소시킴)
  5. 순차적으로 두 숫자의 사이를 좁히면서 만나기 전까지 합이 c 가 되는 모든 경우를 구합니다.


위 풀이를 응용하면 a + b + c = d 또한 구할 수 있습니다.


c 값을 미리 정해두고 a, b 값을 구하면 됩니다.


배열 원소 중 하나를 미리 c 값으로 정해두고 ab 값을 구하는 방식으로 모든 a, b, c 경우의 수를 구할 수 있습니다.


두 용액은 O(n) 이지만 세 용액은 모든 n 에 대하여 두 용액을 한번씩 적용해야되므로 O(n^2) 의 시간 복잡도를 가집니다.


그리고 이 문제는 시간을 줄일 수 있는 요소가 존재합니다.


먼저 숫자에 해당하는 값이 나오면 left 또는 right 중 하나만 바꿀 필요 없이 둘다 바꿔도 됩니다.


a + b = 0 인데 a 나 b 만 바꾸면 0 이 무조건 되지 않기 때문입니다.


두번째로 nums 배열에는 중복값이 존재합니다.


left++ 혹은 right-- 할때 이전값과 비교해서 중복되는 값이 나오지 않을 때까지 계속 패스할 수 있습니다.


[1, 1, 1, 1, 1] 이런 배열이 들어왔을 때 기존 코드는 일일히 비교해야하지만 중복되는 값을 패스하게 하면 처음만 비교하고 나머지는 전부 넘길 수 있습니다.



Java Code

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right] + nums[i];
                
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (nums[left] == nums[left - 1] && left < right) left++;
                    while (nums[right] == nums[right + 1] && left < right) right--;
                } else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return res;
    }
}


+ Recent posts