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개에 도달하면 순회를 그만둬도 될 것 같다.

코딩테스트 연습 - 외벽 점검 | 프로그래머스 스쿨 (programmers.co.kr)

외벽의 총둘레는 n미터. 원형 구조. 취약점 존재

취약점을 점검하기 위해 보내야 하는 친구 수의 최솟값은?

어떤 친구를 어느 지점에 배치해야 할지를 결정해야 하는 문제이다.

원형 외벽을 계산하기 위해 선형으로 변경해야 한다. 배열을 두 배로 늘려 처리할 수 있다.

방향은 따로 고려하지 않아도 된다. 예를 들어 4 → 9 반시계나 9 → 4 시계나 똑같은 범위다.

가장 먼저 떠오르는 것은 dist의 최대가 8이기 때문에 8! 의 모든 경우의 수로 앞에서부터 배치해 가며 들어가는 사람들 확인해 보는 것이다.

1. dist를 통해 순열을 구성한다.
2. 취약점의 시작위치를 변경해 가며 순열을 통해 확인해 본다.
   1. 현재 취약점은 확장돼 있는 상태
   2. 커버한 개수를 통해 모든 지점을 검사했는지 확인해야 한다.
      1. 즉 해당 순열이, 해당 시작점에서, 범위를 커버가능한가 → 3중 루프가 된다.
3. 커버가 가능하다면 답을 갱신한다.

import java.util.*;

class Solution {
    
    int answer = Integer.MAX_VALUE;
    
    public int solution(int n, int[] weak, int[] dist) {
        List<int[]> result = new ArrayList<>();
        permutate(0, new int[dist.length], dist, new boolean[dist.length], result);
        check(n, result, weak);
        
        return answer;
    }
    
    private void check(int n, List<int[]> result, int[] weak) {
        int l = weak.length;
        int[] extendedWeak = extendWeak(n, weak);
        
        for (int[] dist : result) {
            for (int start = 0; start < l; start++) {
                int cnt = 1; // start를 시작점으로 해서 투입한 사람 수
                int end = extendedWeak[start] + dist[cnt - 1];
                for (int i = start; i < start + l; i++) {
                    if (extendedWeak[i] > end) {
                        cnt++; // 추가 투입
                        if (cnt > dist.length) break;
                        end = extendedWeak[i] + dist[cnt - 1];
                    }
                }
                answer = Math.min(answer, cnt);
            }
        }
        
        if (answer > result.get(0).length) answer = -1;
    }
    
    private int[] extendWeak(int n, int[] weak) {
        int l = weak.length;
        int[] extendedWeak = new int[2 * l];
        for (int i = 0; i < l; i++) {
            extendedWeak[i] = weak[i];
            extendedWeak[i + l] = weak[i] + n;
        }
        return extendedWeak;
    }
    
    private void permutate(int depth, int[] selected, int[] dist, boolean[] visited, List<int[]> result) {
        if (depth == dist.length) {
            result.add(selected.clone());
            return;
        }
        
        for (int i = 0; i < dist.length; i++) {
            if (visited[i]) continue;
            selected[depth] = dist[i];
            visited[i] = true;
            permutate(depth + 1, selected, dist, visited, result);
            selected[depth] = 0;
            visited[i] = false;
        }
    }
}

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

수열에서 가장 긴 증가하는 부분 수열의 길이를 출력하라.

배열 nums에서 현재 내 위치 i에서 가장 긴 증가하는 부분 수열은 i보다 앞에 있으면서 nums [i] 보다 값이 작은 부분수열 길이의 최대의 + 1이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static int[] nums;

    static void input() {
        N = scan.nextInt();
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = scan.nextInt();
        }
    }

    public static void main(String[] args) {
        input();
        int[] mem = new int[N+1];
        Arrays.fill(mem, 1);
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    // 앞에있는 거면서 값이 장은 경우
                    mem[i] = Math.max(mem[i], mem[j] + 1);
                }
            }
        }

        int result = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            result = Math.max(result, mem[i]);
        }
        System.out.println(result);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Isomorphic Strings - LeetCode

두 문자열 s, t가 isomorphic 한 지 확인하라.

우선 s와 t의 문자 길이가 다르면 무조건 false이다. 이는 제약조건으로 해결된다.

Isomorphic이기 때문에 각 문자의 대응 문자를 관리해야 한다.

s → t로 하나, t → s로 이렇게 두 개의 변환이 가능해야 하기 때문에 둘을 별도로 관리한다.

만약 해당 문자의 대응 문자가 존재하는 데 다른 대응문자를 넣어야 한다면 false이다.

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> sMap = new HashMap<>();
        Map<Character, Character> tMap = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);

            if (sMap.containsKey(charS)) {
                if (sMap.get(charS) != charT) {
                    return false;
                }
            }
            sMap.put(charS, charT);

            if (tMap.containsKey(charT)) {
                if (tMap.get(charT) != charS) {
                    return false;
                }
            }
            tMap.put(charT, charS);
        }

        return true;
    }
}

Simplify Path - LeetCode

주어진 경로를 정리하는 문제이다.

특이점은 ‘.’과 ‘..’의 처리이다. 주어진 경로를 ‘/’를 기준으로 나누고 Deque를 사용해서 처리하면 될 것이다.

1. 문자열을 ‘/’로 분할한다.
2. Deque에 문자를 넣는다.
3. 이때 처리할 문자가 ‘..’이라면 Deque이 비어있지 않다면 한 번 pop을 한다.
4. 문자가 ‘.’ 이라면 별도 처리를 하지 않는다.
5. 모든 작업이 끝난 뒤 ‘/’를 넣어가며 Deque의 문자들을 앞에서부터 꺼내 완성한다.

class Solution {

    static final String PARENT = "..";
    static final String CURRENT = ".";
    static final String DELIMITER = "/";

    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        for (String s : path.split("/")) {
            if (s.isEmpty()) continue;
            if (s.equals(PARENT)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (s.equals(CURRENT)) {
                continue;
            } else {
                stack.addLast(s);
            }

        }
        StringBuilder sb = new StringBuilder();
        sb.append(DELIMITER);
        while (!stack.isEmpty()) {
            String s = stack.pollFirst();
            sb.append(s).append(DELIMITER);
        }
        if (sb.length() != 1) {
            sb.deleteCharAt(sb.length() - 1);
        }
        
        return sb.toString();
    }
}

Triangle - LeetCode

삼각형 형태의 배열이 주어졌을 때 top에서 bottom까지 최소 합의 경로를 찾아라.

매 단계에서 아래행의 인접한 숫자로 이동할 수 있다. 배열로 치면 현재 (r, c)에 있다고 했을 때 (r + 1, c) 혹은 (r + 1, c + 1)로 이동이 가능한 것이다.

우선 top에서 bottom까지 매 순간 다양한 경로가 존재한다. 먼저 떠오르는 방식은 dfs를 사용하는 완전탐색이다.

하지만 이 방법은 당연하게도 시간초과가 발생한다.

top에서 bottom으로 가는 것을 bottom에서 top으로 간다고 생각해보겠다.

가장 위 (0, 0)의 최소합은 (1, 0), (1,1) 이 두 포인트의 최소합 중 최소에 (0,0) 값을 더한 것이다.

즉 (r, c)의 최소합은 Math.min((r + 1, c), (r + 1, c + 1)) + (r, c)가 된다.

class Solution {
    static final int[][] DIRECTION = {{1, 0}, {1, 1}};
    static final int INF = Integer.MAX_VALUE;

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int[][] mem = new int[triangle.size()][triangle.size()];
        for (int[] row : mem) {
            Arrays.fill(row, INF);
        }
        
        return dfs(0, 0, triangle, mem);
    }

    private int dfs(int r, int c, List<List<Integer>> triangle, int[][] mem) {
        if (r == triangle.size()) {
            return 0;
        }

        if (mem[r][c] != INF) {
            return mem[r][c];
        }

        int min = INF;
        for (int d = 0; d < 2; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];
            
            min = Math.min(min, dfs(nr, nc, triangle, mem));
            
        }
        
        return mem[r][c] = min + triangle.get(r).get(c);
    }
}

top-down방식의 dp이다. 재귀를 통해 하단부터 최솟값을 채워 나갔다.

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] mem = new int[triangle.size()][triangle.size()];
        int n = triangle.size() - 1;
        for (int r = n - 1; r >= 0; r--) {
            for (int c = 0; c < triangle.get(r).size(); c++) {
                triangle.get(r).set(c, Math.min(triangle.get(r+1).get(c), triangle.get(r + 1).get(c + 1)) + triangle.get(r).get(c));
            }
        }

        return triangle.get(0).get(0);
    }
}

bottom-up 방식의 dp이다. 재귀 없이 반복문으로도 처리가 가능하다. 그리고 별도의 배열을 사용하지 않아 공간효율이 늘었다.

https://leetcode.com/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150

1. 우하좌상의 우선순위로 갈 수 있는 동안 진행한다
2. 더 이상 진행할 수 없으면 방향을 전환한다.
3. 네 방향 전부 진행할 수 없다면 최종 종료

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

    public List<Integer> spiralOrder(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        List<Integer> result = new ArrayList<>();
        boolean[][] visited = new boolean[n][m];
        int r = 0;
        int c = 0;
        int d = 0;
        while (true) {
            result.add(matrix[r][c]);
            visited[r][c] = true;
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];

            int cnt = 0;
            while (!isValid(nr, nc, n, m) || visited[nr][nc]) {
                d = (d + 1) % 4;
                nr = r + DIRECTION[d][0];
                nc = c + DIRECTION[d][1];
                cnt++;

                if (cnt >= 4) {
                    return result; 
                }
            }
            r = nr;
            c = nc;
        }
    }

    private boolean isValid(int r, int c, int n, int m) {
        return r >= 0 && r < n && c >= 0 && c < m;
    }
}

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150

오름차순으로 정렬된 nums 배열이 주어졌을 때 이를 height-balanced binary search tree로 변환해라.

균형을 맞추는 것이 중요하다.

어떻게 하면 균형을 맞출 수 있을까?

중간값을 부모로 했을 때 균형이 맞게 된다. 배열의 중간값을 현재 서브트리의 루트로 사용하자.

그리고 왼쪽 절반은 왼쪽 서브트리로, 오른쪽 절반은 오른쪽 서브트리로 재귀적으로 처리하면 될 것 같다.

1. 배열의 중간 인덱스를 찾는다.
2. 중간 요소로 새 노드를 만든다.
3. 왼쪽 절반에 대해 재귀를 통해 왼쪽 자식을 설정한다.
4. 오른쪽 절반에 대해 재귀를 통해 오른쪽 자식을 설정한다.

/**
 * 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 TreeNode sortedArrayToBST(int[] nums) {  
        return constructTree(nums, 0, nums.length - 1);
    }

    private TreeNode constructTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = constructTree(nums, left, mid - 1);
        node.right = constructTree(nums, mid + 1, right);

        return node;
    }

}

https://leetcode.com/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-interview-150

가장 합이 큰 subarray를 찾아라.

subarray를 찾아야 하기 때문에 정렬은 안된다.

가장 단순한 방법은 모든 가능한 부분 배열을 탐색하는 것이다. 물론 이는 배열의 길이가 늘어날수록 아주 비효율적인 알고리즘이 된다.

합을 어떻게 크게 만들 수 있을까. 합은 양수를 더하면 증가하고 음수를 더하면 감소한다.

특정 범위의 합이 음수라면 다음 숫자를 더하는 것 보다 다음 숫자부터 다시 시작하는 것이 맞다는 소리다.

투포인터를 이용하겠다. left,right를 0으로 두고 right로 범위를 확장시켜 나간다.

확장시키면서 최대 합을 갱신한다.

그러다가 합이 음수가 되는 순간 시작점인 left를 변경해 다시 검사를 하는 방식을 사용하겠다.

이 문제에서는 subarray의 범위를 구할 필요는 없어 left를 관리할 필요는 없다.

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            maxSum = Math.max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxSum;
    }
}

그런데 이 문제의 분류를 보니 카데인 알고리즘이라는 내용이 나왔다.

카데인 알고리즘이 뭘까?

카데인 알고리즘은 1차원 배열에서 최대 부분 배열 합을 O(n) 시간 복잡도로 찾는 알고리즘이다.

동적 프로그래밍을 사용한다.

핵임 아이디어는 다음과 같다.

1. 배열을 순회하면서 각 위치에서 끝나는 최대 부분 배열의 합을 계산한다.
2. 각 단계에서 두 가지 선택 중 하나를 한다.
   1. 현재 원소부터 새로운 부분 배열을 시작한다.
   2. 현재 원소를 이전 부분 배열에 추가한다.
3. 이 선택은 현재까지의 합이 양수인가, 음수인가에 따라 결정된다.

설명을 보면 알 수 있듯이 이 문제 자체가 카데인 알고리즘이었다.

현재 위치에서 최대 부분합을 고려하는 부분이 핵심이다.

여기서도 나오는 핵심이 이전까지의 합이 음수이면 현재 요소부터 새로운 부분 배열을 시작하는 것이 이득이다.

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

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

        return maxSum;
    }
}

Divide and Conquer 방식을 사용해서 푸는 방법도 있다.

문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 다음 결과를 합쳐서 전체 문제의 해결책을 얻는 방법이다. 다음과 같은 과정을 거친다.

1. 배열을 두 부분으로 나눈다.
2. 왼쪽 절반의 최대 부분 배열을 찾는다.
3. 오른쪽 절반의 최대 부분 배열을 찾는다.
4. 중간을 가로지르는 최대 부분 배열을 찾는다.
5. 위의 세 경우 중 가장 큰 합을 반환한다.

핵심은 중간을 가로지르는 최대 부분 배열이다. 이는 다음과 같은 과정을 통한다.

1. 중간점에서 왼쪽으로 가며 최대 합을 찾는다.
2. 중간점에서 오른쪽으로 가며 최대 합을 찾는다.
3. 두 합을 더한다.

위의 과정들을 재귀를 통해 배열의 크기가 1이 될 때까지 반복하면 된다.

class Solution {
    public int maxSubArray(int[] nums) {
        return findMaxSubarray(nums, 0, nums.length - 1);
    }

    private int findMaxSubarray(int[] nums, int left, int right) {
        if (left == right) {
            // 배열 크기가 1
            return nums[left];
        }

        int mid = left + (right - left) / 2;

        int leftSum = findMaxSubarray(nums,left, mid);
        int rightSum = findMaxSubarray(nums, mid + 1, right);
        int crossSum = findMaxCrossingSubarray(nums, left, mid, right);

        return Math.max(Math.max(leftSum, rightSum), crossSum);
    }

    private int findMaxCrossingSubarray(int[] nums, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }

        return leftSum + rightSum;
    }
}

https://leetcode.com/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-interview-150

정렬된 배열 nums와 숫자 target이 주어졌을 때 target이 nums에 있다면 해당 인덱스를 없다면 삽입되는 인덱스를 반환하라. 단 O(logN)의 시간복잡도로 풀이해야 한다.

간단하게 O(N)으로 순회하면서 파악하면 답을 구할 수 있다.

하지만 문제 조건에 O(logN)을 요구하고 있으므로 다른 방법을 찾아야 한다.

주어진 조건을 보면 nums 배열은 중복이 없고 오름차순으로 정렬된 배열이다. 따라서 이진탐색을 사용하면 O(logN)의 시간복잡도로 풀 수 있다.

사실 자바에 Collections에 있는 binarySearch 메서드가 이미 위의 조건을 구현하고 있다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        List<Integer> numbers = Arrays.stream(nums)
                                    .boxed()
                                    .collect(Collectors.toList());

        int idx =  Collections.binarySearch(numbers, target);
        return idx < 0 ? -idx - 1 : idx;
    }
}

그렇지만 위의 방법은 Collection에만 사용할 수 있으므로 배열을 List로 변경하는 작업이 추가된다.

따라서 이진탐색을 직접 구현하겠다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        
        while (l <= r) {
            int mid = l - (l - r) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            }
        }
  
        return l;
    }
}