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;
    }
}

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

Trie 자료구조를 구현하는 문제이다.

우선은 Trie에 대해서 알아보고 코드로 구현해 보자.

Trie는 검색 트리의 줄임말로 때로는 접두사 트리라고도 부른다.

기본적으로 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조이다.

각 노드가 문자열을 나타내며 루트에서 특정 노드까지 경로가 하나의 문자열을 형성하는 것이다.

이렇게 하면 얻게 되는 장점이 뭘까?

우선 동일한 접두사를 공유할 수 있다는 점이다.

같은 접두사를 가진 문자열들은 같은 노드들을 공유하고 이는 메모리 사용을 효율적으로 만든다.

다음으로는 검색속도이다.

문자열의 존재 여부를 확인하는 데 O(M)의 시간이 걸린다. (M은 문자열의 길이)

무엇보다 접두사 검색에 최적화 돼 있다.

특정 접두사로 시작하는 모든 문자열을 쉽게 찾을 수 있다.

class Trie {

    static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }

        public Map<Character, TrieNode> getChildren() {
            return children;
        }

        public boolean isEndOfWord() {
            return isEndOfWord;
        }

        public void setEndOfWord(boolean endOfWord)  {
            isEndOfWord = endOfWord;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();    
    }
    
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.getChildren().computeIfAbsent(ch, x -> new TrieNode());
        }
        current.setEndOfWord(true);
    }
    
    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord();
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = searchNode(prefix);
        return node != null;
    }

    private TrieNode searchNode(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            TrieNode node = current.getChildren().get(ch);
            if (node == null) return null;
            current = node;
        }
        return current;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Letter Combinations of a Phone Number - LeetCode

dfs를 통해서 가능한 문자들을 더해나간다.

번호와 문자열을 매칭해야 하는데 어차피 8개밖에 없으니 직접 넣어주는 방식을 선택하겠다.

class Solution {

    static Map<Integer, String> letterMap = new HashMap<>();

    static {
        letterMap.put(2, "abc");
        letterMap.put(3, "def");
        letterMap.put(4, "ghi");
        letterMap.put(5, "jkl");
        letterMap.put(6, "mno");
        letterMap.put(7, "pqrs");
        letterMap.put(8, "tuv");
        letterMap.put(9, "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        if (digits.equals("")) return List.of();

        List<String> result = new ArrayList<>();
        dfs(0, "", digits, result);
        return result;    
    }

    private void dfs(int depth, String curr, String digits, List<String> result) {
        if (depth == digits.length()) {
            result.add(curr);
            return;
        }

        int key = digits.charAt(depth) - '0';
        for (String s : letterMap.get(key).split("")) {
            dfs(depth + 1, curr + s, digits, result);
        }
    }
}