Coin Change - LeetCode

amount를 만드는데 필요한 최소 코인 개수를 찾아야 한다.

coins = [1, 2, 5], amount = 11 일 때

11 = 5 + 5 + 1 이 최소이다. 답은 3이다.

coins = [2], amount = 3 일 때

3은 2를 통해 만들 수 없기 때문에 -1이 답니다.

coins = [1], amount = 0이면 0개를 사용하면 되기 때문에 답은 0이다.

우선 greedy를 고려해 볼 수 있지만 각 동전은 대체가 불가능하기 때문에 최적해를 보장할 수 없다.

dp를 생각해 보자.

dp [i] = i원을 만드는데 필요한 최소 동전 개수이다.

첫 번째 예시에서 dp [11] = min(dp [6], dp [9], dp [10]) + 1 이렇게 된다.

정리하자면 dp [i] = min(dp [i], dp [i-coin] + 1), for coin in coins, dp [0] = 0이 된다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i-coin] != INF) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); 
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

Min Stack - LeetCode

stack을 구현하는 문제이다. 모든 작업이 O(1)의 시간복잡도로 가능해야 한다.

대부분의 기능은 stack을 쓰면 O(1)이 가능하지만 최솟값을 알아내야 하는 기능도 O(1)로 동작해야 한다는 점이 중요하다.

우선 최소값을 변수로 저장하는 방법을 생각해 보자.

이 방법은 최솟값을 바로 찾을 수는 있지만 최솟값이 갱신될 때 스택 내의 모든 요소를 순회해야 한다.

별도로 해당 레벨에서의 최솟값을 가지고 있어야 할 객체가 필요하다.

즉 삽입되는 값을 노드라고 생각했을 때 항상 노드 기준 최소값을 함께 기억하고 있는 것이다.

class MinStack {

    static class Node {
        int val;
        int min;

        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    private Deque<Node> stack = new LinkedList<>();

    public MinStack() {
    }
    
    public void push(int val) {
        if (!stack.isEmpty()) {
            Node top = stack.peekLast();
            stack.addLast(new Node(val, Math.min(val, top.min)));
            return;
        }
        stack.addLast(new Node(val, val));
    }
    
    public void pop() {
        stack.pollLast();
    }
    
    public int top() {
        return stack.peekLast().val;
    }
    
    public int getMin() {
        return stack.peekLast().min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Search a 2D Matrix - LeetCode

m x n 2차원 배열인 matrix에 target에 존재하는지 확인하는 문제이다.

matrix에는 특징이 있는데 각각의 row는 오름차순으로 정렬 돼 있고 각 row의 첫 번째 값은 이전 row의 마지막 값보다 크다.

O(log(m*n))의 시간 복잡도로 해결해야 한다.

matrix의 조건을 보면 알 수 있듯이 결국 정렬된 상태라는 소리다.

flatMap으로 1차원으로 변경할 수 있으면 좋지만 시간복자도 제한 때문에 불가능하다. 그렇지만 이미 정렬된 상태이기 때문에 2D인 채로 이진 탐색이 가능하다.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        return binarySearch(matrix, 0, m * n - 1, target, m, n) < 0 ? false : true;
    }

    private int binarySearch(int[][] arr, int left, int right, int target, int m, int n) {
        if (left > right) return -1;

        int mid = left - (left - right) / 2;
        int value = arr[mid / n][mid % n];

        if (value == target) {
            return mid;
        } else if (value < target) {
            return binarySearch(arr, mid + 1, right, target, m, n);
        } else {
            return binarySearch(arr, left, mid - 1, target, m, n);
        }
    }
}

Plus One - LeetCode

단순하게 배열을 숫자로 변환하고 +1 한 다음 다시 배열로 변환하는 방식의 경우 배열의 최대 길이가 100이기에 long의 범위를 넘어선다.

따라서 배열의 값들이 0~9 사이 이기 때문에 carry를 통해 계산을 처리하는 방식으로 진행한다.

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        List<Integer> result = new ArrayList<>();
        int carry = 1;

        for (int i = n - 1; i >= 0; i--) {
            int num = digits[i];
            if (num + carry >= 10) {
                result.add(num + carry - 10);
            } else {
                result.add(num + carry);
                carry = 0;
            }            
        }

        if (carry != 0) {
            result.add(carry);
        }

        int[] answer = new int[result.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = result.get(answer.length - 1 - i);
        }

        return answer;
    }
}

House Robber - LeetCode

인접한 두 집을 털 수는 없다.

[1, 2, 3, 1]이라면 0번과 2번을 털면 4라는 최대 수익을 낼 수 있다.

즉 해당 위치의 집을 털거나 털지 않거나 둘 중 하나의 경우가 존재한다.

i위치에서의 최대는 i-1을 털었을 떄와 i-2를 털고 i를 털었을 때의 최대가 된다.

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[nums.length - 1];
    }
}

Surrounded Regions - LeetCode

‘X’, ‘O’로 이루어진 m x n 2차원 배열이 있다.

사방이 ‘X’로 둘러 쌓여있는 ‘O’들은 ‘X’로 변경한 결과를 반환하라.

‘X’는 언제 ‘O’로 변경되는가? ‘O’가 ‘X’로 둘러 쌓여 있을 때 변경된다.

가장자리의 ‘O’에 연결된 부분은 절대로 ‘X’로 바뀌지 않는다. 그 이외의 ‘O’들은 전부 ‘X’로 바뀔 수밖에 없다.

즉 가장자리에 존재하는 ‘O’ 부터 시작해서 탐색을 진행하며 해당 위치를 별도로 표기해 두고 나머지를 전부 ‘X’로 채우면 된다.

1. 가장자리를 탐색하면서 ‘O’라면 탐색을 시작한다.
2. 탐색 과정에서는 ‘O’를 임시로 ‘A’로 바꿔놓는다.
3. 모든 탐색이 끝난 후 ‘X’로 가득 차 있는 2차원 배열에서 ‘A’의 위치를 ‘O’로 변경해 리턴한다.

class Solution {
    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public void solve(char[][] board) {
        Set<int[]> startPoints = getStartPoints(board);
        for (int[] startPoint : startPoints) {
            dfs(startPoint, new boolean[board.length][board[0].length], board);
        }

        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (board[r][c] =='O') {
                    board[r][c] = 'X';
                } else if (board[r][c] == 'A') {
                    board[r][c] = 'O';
                }
            }
        }
    }

    private void dfs(int[] currPoint, boolean[][] visited, char[][] board) {
        int r = currPoint[0];
        int c = currPoint[1];
        board[r][c] = 'A';
        visited[r][c] = true;

        for (int d = 0; d < 4; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];

            if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
            if (board[nr][nc] == 'O' && !visited[nr][nc]) {
                dfs(new int[]{nr, nc}, visited, board);
            }
        }
    }

    private Set<int[]> getStartPoints(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        Set<int[]> result = new HashSet<>();
        for (int row : List.of(0, n - 1)) {
            for (int col = 0; col < m; col++) {
                if (board[row][col] == 'O') {
                    result.add(new int[]{row, col});
                }
            }
        }

        for (int col : List.of(0, m - 1)) {
            for (int row = 0; row < n; row++) {
                if (board[row][col] == 'O') {
                    result.add(new int[]{row, col});
                }
            }
        }

        return result;
    }
}

Minimum Genetic Mutation - LeetCode

‘A’, ‘C’, ‘G’, ‘T’로 이루어진 8글자 문자열

startGene에서 endGene으로 변형하는데 필요한 최소 변경 횟수를 찾으시오. 없다면 -1

한 번에 하나의 문자만 변경이 가능하며 변경된 유전자 문자열은 bank에 반드시 존재해야 한다.

startGene에서부터 탐색을 시작해서 첫 글자부터 ‘A’, ‘C’, ‘G’, ‘T’로 바꿔가면서 탐색을 진행한다.

최소 횟수를 구하고 있기 때문에 BFS를 통해 처리하겠다.

현재 상태에서 위치의 문자를 변경해 가며 bank에 존재한다는 조건에 맞다면 q에 집어넣는다.

class Solution {

    static final char[] GENES = {'A', 'C', 'G', 'T'};

    static class Mutate {
        String gene;
        int count;

        public Mutate(String gene, int count) {
            this.gene = gene;
            this.count = count;
        }
    }

    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = Arrays.stream(bank).collect(Collectors.toSet());
        Set<String> visited = new HashSet<>();
        if (!bankSet.contains(endGene)) return -1;
        Queue<Mutate> q = new LinkedList<>();
        q.add(new Mutate(startGene, 0));
        visited.add(startGene);

        while (!q.isEmpty()) {
            Mutate curr = q.poll();
            if (curr.gene.equals(endGene)) {
                return curr.count;
            }
            StringBuilder sb = new StringBuilder(curr.gene);
            for (int i = 0 ; i < 8; i++) {
                for (char c : GENES) {
                    StringBuilder next = new StringBuilder(sb);
                    if (next.charAt(i) != c) {
                        next.setCharAt(i, c);
                        if (visited.contains(next.toString())) continue;
                        if (bankSet.contains(next.toString())) {
                            q.add(new Mutate(next.toString(), curr.count + 1));
                            visited.add(next.toString());
                        }
                    }
                }
            }
        }

        return -1;
    }
}

Add Two Numbers - LeetCode

두 연결리스트를 가지고 합을 계산해야 한다.

일종의 후위표기법이다. [2, 4, 3], [5, 6, 4] 이렇게 주어졌을 때 342 + 465 = 807이 되어 결과는 [7, 0, 8]이 정답이 된다.

길이가 다른 경우도 생각해 보자.

[2, 4, 3], [5, 7]이다. 이러면 342 + 75 = 417이 되고 [7, 1, 4]가 정답이 된다.

우선 자리 올림수(carry)가 발생한 경우를 생각해야 한다.

1. 두 연결리스트에서 값을 꺼낸다
2. 값을 더해 노드를 만든다.
3. 이때 캐리가 발생했다면 다음에 더하기 위해 기록해 둔다.
4. 캐리는 합을 10으로 나눈 몫이고 자릿수는 합을 10으로 나눈 나머지이다.
5. 반복이 끝났을 때 캐리가 남아있다면 추가해 준다.

/**
 * 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 head = new ListNode();
        ListNode curr = head;
        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;
            }
            
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            curr.next = node;
            curr = curr.next;
        }

        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return head.next;
    }
}

Average of Levels in Binary Tree - LeetCode

이진트리의 root가 주어졌을 때 각 레벨의 평균값을 담은 List를 반환하라.

예를 들어 [3, 9, 29, null, null, 15, 7]의 트리라면 레벨 1은 3.00000, 레벨 2는 (9 + 29) / 2 = 14.5000, 레벨 3은 (15 + 7) / 2 = 11.00000 이 된다.

레벨별로 어떤 노드들이 존재하는지를 파악해야 한다.

큐를 통해 해결할 수 있을 것 같다.

1. 루트 노드를 큐에 넣는다.
2. 큐에서 노드를 꺼낸다.
3. left, right를 보고 자식의 개수를 기록한다.
4. 자식들을 큐에 넣는다.
5. 반복을 통해 자식의 개수만큼 큐에서 꺼내면서 평균을 계산한다.
6. 자식들을 큐에 넣고 다음 반복에서는 이번에 기록된 자식의 개수만큼 처리를 한다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        List<Double> result = new ArrayList<>();

        double sum = 0.0;
        int cnt = 1;
        while (!q.isEmpty()) {
            int count = 0;
            for (int i = 0; i < cnt; i++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null) {
                    q.add(node.left);
                    count++;
                }
                if (node.right != null) {
                    q.add(node.right);
                    count++;
                }     
            }
            result.add(sum / cnt);
            sum = 0;
            cnt = count;
        }

        return result;
    }
}

Kth Smallest Element in a BST - LeetCode

이진 탐색 트리의 root가 주어졌을 때, k번째로 작은 값을 반환하라.

예를 들어 트리가 [3, 1, 4, null, 2]이고 k = 1이라면 가장 작은 값이니 1이 정답이 된다.

다음으로 [5, 3, 6, 2, 4, null, null, 1] 이고 k = 3이면 1, 2, 3으로 3이 정답이 된다.

주어진 자료구조가 BST(이진 탐색 트리)인 점을 주목해야한다.

이진 탐색 트리는 중위순회를 했을 시 데이터가 정렬된 채로 반환이 된다.

그렇다면 중위순회를 통해 정렬된 1차원 데이터를 얻고 거기서 k번 째 값을 반환하면 될 것이다.

1. 중위순회를 통해 List <Integer>를 구성한다.
2. 해당 List에서 k번째 값을 반환한다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> numbers = new ArrayList<>();
        inOrder(root, numbers);
        return numbers.get(k - 1);
    }
    
    private void inOrder(TreeNode node, List<Integer> numbers) {
        if (node == null) {
            return;
        }

        inOrder(node.left, numbers);
        numbers.add(node.val);
        inOrder(node.right, numbers);
    }
}

굳이 전체를 순회하지 않더라도 k개만 순회하고 k개에 도달하면 순회를 그만둬도 될 것 같다.