꿀잠

https://leetcode.com/problems/word-search-ii/description/

보드의 문자열을 순회하며 단어를 만들 수 있는지 확인하는 문제이다.
보드의 문자를 순차적으로 연결하는 문제이기에 초기에 백트래킹을 이용하여 해결하려고 시도했다.

하지만 찾아야 하는 단어가 배열로 많이 주어지고,같은 prefix를 갖는 단어들이 주어지는 테스트 케이스가 존재하여 시간 초과가 되었다. 이를 해결하기 위해 Trie 자료구조를 이용했다. 아래는 완성한 통과 코드이다.

import java.util.*;  
  
public class Solution {  
  
    Set<String> answerSet;  
    char[][] board;  
    boolean[][] visited;  
    int[] dr = {-1, 0, 1, 0};  
    int[] dc = {0, -1, 0, 1};  
    int m;  
    int n;  
  
    public List<String> findWords(char[][] board, String[] words) {  
        this.board = board;  
        this.m = board.length;  
        this.n = board[0].length;  
        this.visited = new boolean[m][n];  
        TrieNode root = new TrieNode();  
        answerSet = new HashSet<>();  
  
        for(String word: words){  
            TrieNode head = root;  
            for(int i = 0; i < word.length(); i++){  
                char c = word.charAt(i);  
                int check = c - 'a';  
                if(head.next[check] == null){  
                    head.next[check] = new TrieNode();  
                }  
                TrieNode next = head.next[check];  
  
                head = next;  
                if(i == word.length() - 1){  
                    head.isLast = true;  
                }  
            }  
        }  
  
        StringBuilder sb = new StringBuilder();  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                visited[i][j] = true;  
                sb.append(board[i][j]);  
                findWord(root, i, j, sb);  
                visited[i][j] = false;  
                sb.setLength(sb.length() - 1);  
            }  
        }  
  
        return new ArrayList<>(answerSet);  
    }  
  
    private void findWord(TrieNode head, int r, int c, StringBuilder sb){  
        char ch = board[r][c];  
        int check = ch - 'a';  
        if(head.next[check] == null){  
            return;  
        }  
  
        head = head.next[check];  
  
        if(head.isLast){  
            answerSet.add(sb.toString());  
        }  
  
        for(int k = 0; k < dr.length; k++){  
            int nextRow = r + dr[k];  
            int nextCol = c + dc[k];  
            if(nextRow >= 0 && nextRow < m  
                    && nextCol >= 0 && nextCol < n  
                    && !visited[nextRow][nextCol]){  
                visited[nextRow][nextCol] = true;  
                sb.append(board[nextRow][nextCol]);  
                findWord(head, nextRow, nextCol, sb);  
                visited[nextRow][nextCol] = false;  
                sb.deleteCharAt(sb.length() - 1);  
            }  
        }  
    }  
  
    private static class TrieNode{  
        TrieNode[] next;  
        boolean isLast;  
  
        TrieNode(){  
            next = new TrieNode[26];  
            isLast = false;  
        }  
    }  
  
}

중복되는 정답을 정리하기 위해 Set을 이용해주었다. 해결한 이후 보다 빠른 통과 코드를 확인해보았다. 다른 점은 TrieNode에 isLast 대신 String word를 넣어주는 방법이었다. word를 저장시 isLast 지점에서 word 자체를 저장하는 방식이었다.

    private static class TrieNode{  
        TrieNode[] next;  
        String word;  
  
        TrieNode(){  
            next = new TrieNode[26];   
        }  
    }  
}

해당 클래스에 word를 넣어주면 백트래킹 탐색시 문자열 검색이 쉬워지는 장점이 있다. 또한 Set을 이용할 필요 없이 word를 지워주는 방식으로 중복을 제거할 수 있었다. Trie 구조가 익숙하지 않았었기에 새로운 사용 방식을 배울 수 있었다.

https://leetcode.com/problems/permutations/

주어진 배열의 순열을 모두 뽑아내는 문제이다. 가장 기본적인 형태의 알고리즘의 문제이다.
주어진 배열을 직접 스왑하면서 푸는 방식도 있지만 일반적인 백트래킹 방식으로도 해결할 수 있다.

백트래킹을 할 때는 항상 재귀 함수 이후 원 상태로 돌려주어야 한다는 점이다. 아래는 통과한 전체 코드이다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> permute(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> list = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(nums, list, answer, visited);  
  
        return answer;  
    }  
  
    private void dfs(int[] nums, List<Integer> cur, List<List<Integer>> answer, boolean[] visited){  
        if(cur.size() == nums.length){  
            answer.add(new ArrayList<>(cur));  
            return;  
        }  
  
        for(int i = 0; i < nums.length; i++){  
            if(!visited[i]){  
                visited[i] = true;  
                cur.add(nums[i]);  
                int removeIdx = cur.size() - 1;  
                dfs(nums, cur, answer, visited);  
                cur.remove(removeIdx);  
                visited[i] = false;  
            }  
        }  
    }  
}

https://ygs3004.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F

주어지는 Task를 실행하기 위한 시간을 구하는 문제이다. 같은 Task를 실행하기 위해선 n 만큼의 시간이 지나야 한다는 제한 조건이 있다.

Task를 실행하기 위하여 반복되는 Task를 우선 실행하게 하기로 했다. PriorityQueue를 이용하여 Task의 repeat을 기준으로 정렬 되도록 하였다. 단 이때 n 만큼의 시간이 더 필요한 경우를 체크해야 했기 때문에 현재 실행이 불가능한 경우는 next로 이동시켜 주었다. 모든 Task가 실행이 불가능한 경우 next로 전부 이동이 되며 while 문이 종료된다. 이 때는 다음 루프로 cnt가 증가하며 idle이 실행된 것으로 간주할 수 있다. 실행 가능한 Task가 있을 경우 해당 task를 poll한 상태로 나머지를 next로 이동시켜 주어서 문제를 해결했다.

import java.util.*;  
  
public class Solution {  
    public int leastInterval(char[] tasks, int n) {  
        PriorityQueue<Task> pq = new PriorityQueue<>();  
        int[] repeats = new int[26];  
  
        // 문자별 반복 횟수 체크  
        for(int i = 0; i < tasks.length; i++){  
            char c = tasks[i];  
            repeats[c - 'A']++;  
        }  
  
        // 문자 반복 및 값 정보 pq 에 삽입,  
        // n의 최대값이 100이므로 초기 lastIdx를 충분히 낮은 값인 -101로 주었다.  
        // Integer.MIN_VALUE 처럼 극한 값을 주면 오버플로우 발생 가능  
        for(int i = 0; i < repeats.length; i++){  
            if(repeats[i] > 0){  
                char c = (char)(i + 'A');  
                pq.add(new Task(repeats[i], c, -101));  
            }  
        }  
  
        int cnt = 0;  
        while(!pq.isEmpty()){  
            PriorityQueue<Task> next = new PriorityQueue<>();  
            cnt++;  
  
            // 실행 할수 있는 Task 가 있는지 확인  
            while(!pq.isEmpty()){  
                Task task = pq.poll();  
                int lastIdx = task.lastIdx;  
                if(cnt - lastIdx > n){  
                    task.lastIdx = cnt;  
                    task.repeat--;  
  
                    if(task.repeat > 0){  
                        next.add(task);  
                    }  
                    break;  
  
                }  
                // Task 가 next로 전부 이동될 동안 실행 불가능할 경우 idle                
                next.add(task);  
            }  
  
            // 나머지 Task next 로 이동  
            while(!pq.isEmpty()){  
                next.add(pq.poll());  
            }  
  
            // next pq를 이용하여 다음 체크  
            pq = next;  
        }  
  
        return cnt;  
    }  
  
    private static class Task implements Comparable<Task>{  
        int repeat;  
        char value;  
        int lastIdx;  
  
        Task(int repeat, char value, int lastIdx){  
            this.repeat = repeat;  
            this.value = value;  
            this.lastIdx = lastIdx;  
        }  
  
        @Override  
        public int compareTo(Task o){  
            return Integer.compare(o.repeat, this.repeat);  
        }  
    }  
}

코드를 완성하고 나서 결과가 다른 정답 코드에 비해 느린 편으로 나왔다. 다른 코드의 방식은 규칙성을 이용해 일종의 수학적 공식을 만드는 방식이었다. 하지만 실제 해당 코드에서 task가 진행되는 동안에 추가적인 동작이 필요하다면 이용할 수 없기에 좋은 방법은 아닌듯하다. 수학적인 방식이 아니라 프로그래밍 방식의 해결 방법을 위해서는 PriorityQueue를 쓰는게 좋은 풀이라고 생각한다.

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

이진 트리에서 두 노드의 공통 조상 중 가장 가까운 공통 조상을 찾는 문제이다.

이진트리의 경우 좌측 노드는 현재의 값보다 작으며 우측 노드는 현재의 값보다 크다는 특징이 있다. 특정 두 노드의 공통 조상 중 가장 가까운 조상일 경우 해당 노드를 기준으로 좌, 우측에 두 노드가 있게 된다. 따라서 해당 조건으로 루트에서 노드를 따라 찾아가면 찾을 수 있다.

/**  
 * Definition for a binary tree node. * public class TreeNode { 
   *     int val; 
   *     TreeNode left; 
   *     TreeNode right; 
   *     TreeNode(int x) { val = x; } 
   * } 
   */  
class Solution {  
  
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        int pVal = p.val;  
        int qVal = q.val;  
  
        while(root != null){  
            int curVal = root.val;  
            // 두 값 모두 현재 노드에서 왼쪽에 있는 경우.
            if(curVal > pVal && curVal > qVal){  
                root = root.left;  
			// 두 값 모두 현재 노드에서 오른쪽에 있는 경우.
            }else if(curVal < pVal && curVal < qVal){  
                root = root.right;  
            }else{  
                return root;  
            }  
        }  
  
        return root;  
    }  
  
}

https://leetcode.com/problems/linked-list-cycle/description/

LinkedList 가 사이클을 이루며 이어져 있는지 체크하는 문제이다.
중복 체크를 위해선 가장 편한 방법 중 하나인 Set을 사용해주었다.
난이도는 특별히 높지 않았다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;  
  
public class Solution {  
    public boolean hasCycle(ListNode head) {  
        Set<ListNode> set = new HashSet<>();  
        while(head != null){  
            if(set.contains(head)){  
                return true;  
            }  
            set.add(head);  
            head = head.next;  
        }  
  
        return false;  
    }   
}

다른 사람의 솔루션으로 속도가 좋은 방식으로는 아래와 같은 방식이 있었다. 별도의 자료구조를 사용하지 않고 두 개의 참조 값을 변화하며 비교만 하기에 속도가 뛰어났고 아이디어가 좋아 보였다.

public class Solution {
    public boolean hasCycle(ListNode head) {
        
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow = head;

        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                return true;
            }
            
        }
         return false;
    }
}

https://leetcode.com/problems/minimum-window-substring/description/

두 문자열이 주어질 때 두번째 문자열이 첫번째 문자열에 모두 포함될 수 있는 최소 길이를 찾는 문제이다.

부분 문자열을 찾기 위해 좌우측 끝을 슬라이딩 하며 찾아주었다. 이 때 문자열이 포함되는지 여부는 Map 자료구조를 이용해 주었다. 중복되는 문자도 있을 수 있으므로 Map의 Key를 문자로 하고 반복 값을 Value로 해주었다.

우측을 증가 시키며 문자열을 확인해 주었으며, 문자열이 확인된 이후에는 좌측을 증가 시켜 문자의 최소 길이를 측정해주었다. 완성된 코드는 아래와 같다.

  
import java.util.*;  
  
public class Solution {  
    public String minWindow(String s, String t) {  
  
        // t의 문자열 정보 저장  
        Map<Character, Integer> chkMap = new HashMap<>();  
        for(char c : t.toCharArray()){  
            chkMap.put(c, chkMap.getOrDefault(c, 0) + 1);  
        }  
  
        // 슬라이딩 되는 문자열 저장  
        Map<Character, Integer> curMap = new HashMap<>();  
  
        // t의 문자열의 총 개수  
        int complete = t.length();  
        // t의 문자열과 현재 슬라이딩 중인 문자열의 개수가 같은 정도  
        int maked = 0;  
        String answer = "";  
  
        // 좌측  
        int l = 0;  
        // 우측을 증가시키며 체크  
        for(int r = 0; r < s.length(); r++){  
            char right = s.charAt(r);  
            // 현재 우측 문자의 포함여부 확인  
            if(chkMap.containsKey(right)){  
                int value = chkMap.get(right);  
                int curValue = curMap.getOrDefault(right, 0) + 1;  
                curMap.put(right, curValue);  
                // 동일 문자가 나오는 경우 필요한 문자인지 체크  
                if(curValue <= value) maked++;  
            }  
  
            // 좌측 문자의 최대값 찾기  
            while(complete == maked){  
                String now = s.substring(l, r + 1);  
                answer = answer.length() == 0 || now.length() < answer.length() ? now : answer;  
  
                char left = s.charAt(l);  
                if(chkMap.containsKey(left)){  
                    int value = chkMap.get(left);  
                    int curValue = curMap.get(left) - 1;  
                    curMap.put(left, curValue);  
                    if(curValue < value) maked--;  
                }  
  
                // 우측이 고정된 상태에서 좌측을 증가시키며 체크  
                l++;  
            }  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

값이 정렬된 배열이 존재할 때 이 배열을 왼쪽으로 회전 시킨 배열이 매개 변수로 주어진다.
원본 배열의 최소 값이자 0번 인덱스의 값은 무엇인지 찾는 문제이다. 이진 탐색을 이용하여 해결할 수 있고 mid 값을 기준으로 왼쪽, 또는 오른쪽은 정확히 정렬되어있다는 점을 이용해 반복 탐색할 수 있다.

왼쪽으로 회전 되기 때문에 만약 우측 끝 값이 중앙 값보다 크다면 우측 부분은 제대로 정렬되어 있다고 할 수 있다. 이 때 우측이 제대로 정렬 되어 있다면 현재의 mid가 원점이 될 수 있다는 점을 생각해 탐색을 할 때 현재 mid 값을 이어 가야 한다. 아래는 최종 코드이다.

public class Solution {  
    public int findMin(int[] nums) {  
        int l = 0;  
        int r = nums.length - 1;  
        int mid = (l + r) / 2;  
  
        while(l <= r){  
            mid = l + (r - l) / 2;  
            int n = nums[mid];  
  
            // 오른쪽이 정렬  
            if(n < nums[r]){  
                r = mid;  
            // 왼쪽이 정렬된 경우  
            }else{  
                l = mid + 1;  
            }  
        }  
  
        return nums[mid];  
    }  
  
}

https://leetcode.com/problems/daily-temperatures/description/

주어진 온도 배열에서 현재의 온도보다 값이 늘어나기 까지 걸리는 일 수를 구하는 문제이다.
인덱스를 늘리며 스택에 온도가 낮은 경우를 저장해 가며 해결하면 효율적으로 해결할 수 있다.

온도가 올라간 날짜(인덱스)의 경우 스택에서 차례대로 제거되기 때문에 스택에서 제거 가능할 때까지 반복하고, 신규 값을 스택에 넣어주면 된다. int[] 타입을 써도 되지만 가독성과 편의성을 위해 인덱스를 저장하는 별도의 클래스를 만들었다.

완성 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int[] dailyTemperatures(int[] temperatures) {  
  
        int[] answer = new int[temperatures.length];  
        Deque<IdxTemp> stack = new ArrayDeque<>();  
  
        for(int i = 0; i < temperatures.length; i++){  
            int curTemp = temperatures[i];  
  
            // 현재보다 낮은 온도의 이전의 값들을 제거하며 답에 저장  
            while(!stack.isEmpty() && stack.peekLast().temp < curTemp){  
                IdxTemp lowTemp = stack.pollLast();  
                answer[lowTemp.idx] = i - lowTemp.idx;  
            }  
  
            stack.addLast(new IdxTemp(i, curTemp));  
        }  
        return answer;  
    }  
  
    private static class IdxTemp{  
        int idx;  
        int temp;  
  
        IdxTemp(int idx, int temp){  
            this.idx = idx;  
            this.temp = temp;  
        }  
    }  
}