꿀잠

https://leetcode.com/problems/min-cost-to-connect-all-points/description/

좌표의 거리가 가장 가까운 거리에 있는 좌표끼리 이어주는 문제이다. 최소신장트리 알고리즘이 필요한 문제이다. 좌표간의 거리는 일반적인 거리가 아닌 manhattan distance를 이용해야 하며 문제에서 수식이 주어진다.

최소 신장 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 대표적이다. 그 중 프림 알고리즘을 이용하여 풀어주었다.

프림 알고리즘은 임의의 한 지점부터 가장 가까운 거리에 있는 지점을 이어주면서 순차적으로 방문한 지점들을 visited로 체크해주는 방식이다. 순차적으로 가까운 거리를 이어주기 위해서 PriorityQueue를 사용해 주었고 주어진 수식을 이용하기 위해 Comparable을 구현한 클래스를 만들어주었다.

import java.util.*;  
  
public class Solution {  
    public int minCostConnectPoints(int[][] points) {  
  
        int answer = 0;  
        boolean[] visited = new boolean[points.length];  
        PriorityQueue<Edge> pq = new PriorityQueue<>();  
        pq.add(new Edge(0, 0, points));  
  
        while(!pq.isEmpty()){  
            Edge edge = pq.poll();  
            int cur = edge.to;  
            if(visited[cur]) continue;  
            visited[cur] = true;  
            answer += edge.dist;  
  
            for(int next = 0; next < points.length; next++){  
                if(next == cur) continue;  
                if(!visited[next]){  
                    pq.add(new Edge(cur, next, points));  
                }  
            }  
        }  
  
        return answer;  
    }  
  
    private static class Edge implements Comparable<Edge>{  
        int from;  
        int to;  
        int dist;  
  
        Edge(int from, int to, int[][] points){  
            this.from = from;  
            this.to = to;  
            this.dist = manDist(points[from], points[to]);  
        }  
  
        private int manDist(int[] from, int[] to){  
            int xCalc = Math.abs(from[0] - to[0]);  
            int yCalc = Math.abs(from[1] - to[1]);  
            return xCalc + yCalc;  
        }  
  
        @Override  
        public int compareTo(Edge o){  
            return this.dist - o.dist;  
        }  
  
    }  
  
}

https://leetcode.com/problems/clone-graph/description/

주어진 그래프 노드를 깊은 복사 하는 함수를 만드는 문제이다.
깊은 복사를 해야 하므로 주어진 클래스와 연결된 노드는 모두 새로 생성되고 값을 복사해야한다.
주어진 조건으로 1 ~ 100 까지이고, 각 노드는 유니크 하다는 조건을 이용해 copy 배열과 bfs를 만들어서 이용해주었다.

package ygs.leetcode.main.problem.graphs.cloneGraph;  
  
/*  
// Definition for a Node.  
class Node {  
    public int val;    
    public List<Node> neighbors;    
    public Node() {        
	    val = 0;        
	    neighbors = new ArrayList<Node>();    
	}    
	
	public Node(int _val){
	        val = _val;
	        neighbors = new ArrayList<Node>();    
	}    
	
	public Node(int _val, ArrayList<Node> _neighbors) {        
		val = _val;        
		neighbors = _neighbors;    
	}}  
*/  
  
import java.util.*;  
  
public class Solution {  
    public Node cloneGraph(Node node) {  
        if(node == null) return null;  
  
        Node[] copys = new Node[101];  
        List[] copyLists = new ArrayList[101];  
        boolean[] visited = new boolean[101];  
  
        Queue<Node> que = new ArrayDeque<>();  
        que.add(node);  
  
        while(!que.isEmpty()){  
            Node origin = que.poll();  
            List<Node> orgNeighbors = origin.neighbors;  
  
            if(visited[origin.val]) continue;  
            visited[origin.val] = true;  
  
            Node copy = getOrCreate(copys, origin.val);  
            copyLists[origin.val] = copy.neighbors;  
            List<Node> copyList = copyLists[origin.val];  
  
            copys[origin.val].neighbors = copyLists[origin.val];  
  
            for(Node originNeighbor: orgNeighbors){  
                int neighborVal = originNeighbor.val;  
                copyList.add(getOrCreate(copys, neighborVal));  
  
                if(!visited[originNeighbor.val]){  
                    que.add(originNeighbor);  
                }  
            }  
        }  
  
        return copys[node.val];  
    }  
  
    private Node getOrCreate(Node[] copys, int val){  
        if(copys[val] == null){  
            copys[val] = new Node(val);  
        }  
  
        return copys[val];  
    }  
}

문자열을 검색하는 커스텀 클래스를 만드는 문제이다.
Trie 자료구조를 이용해서 문제를 해결할 수 있다. Trie 자료구조란 문자열을 저장할 때 각 노드에 대한 자식 노드를 포인트 배열로 저장하는 형식이다.

해당 문제에선 "." 일 경우 검색 시 모든 문자가 가능하다는 조건이 있고 해당 부분이 문제의 핵심 부분이다. 조건문을 이용하여 해당 부분을 분기 처리하여 해결하였다. 노드를 List 형식으로 하여 순회하였으며, "." 일 경우 연결되는 모든 노드를 List에 전부 추가하여 주었다.

모든 순회가 끝난 이후 마지막 노드들 중 isLast가 있을 경우 검색이 성공한 것이므로 True를 반환하였다. 만약 최종 순회 후 List가 비어있을 경우 result의 초기 값인 false가 반환되며 이는 주어진 문자열에 알맞게 마지막까지 이어지는 글자가 없는 것을 의미한다.

import java.util.*;  
  
class WordDictionary {  
  
    WordNode root;  
  
    public WordDictionary() {  
        this.root = new WordNode();  
    }  
  
    public void addWord(String word) {  
  
        WordNode before = this.root;  
  
        for(int i = 0; i < word.length(); i++){  
            int cur = word.charAt(i) - 'a';  
  
            if(before.next[cur] == null){  
                before.next[cur] = new WordNode();  
            }  
  
            before = before.next[cur];  
        }  
  
        before.isLast = true;  
    }  
  
    public boolean search(String word) {  
        List<WordNode> beforeList = new ArrayList<>();  
        WordNode start = this.root;  
        beforeList.add(start);  
        boolean result = false;  
        for(int i = 0; i < word.length(); i++){  
            char cur = word.charAt(i);  
            List<WordNode> nextList = new ArrayList<>();  
  
            for(WordNode before : beforeList){  
                if(cur == '.'){  
                    for(int j = 0; j < 26; j++){  
                        WordNode next = before.next[j];  
                        if(next != null){  
                            nextList.add(next);  
                        }  
                    }  
                }else{  
                    WordNode next = before.next[cur - 'a'];  
                    if(next != null){  
                        nextList.add(next);  
                    }  
                }  
  
            }  
            beforeList = nextList;  
        }  
  
        for(WordNode next: beforeList){  
            result = result || next.isLast;  
        }  
  
        return result;  
    }  
  
    private static class WordNode{  
        WordNode[] next;  
        boolean isLast;  
  
        WordNode(){  
            this.next = new WordNode[26];  
            isLast = false;  
        }  
    }  
}  
  
/**  
 * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */

https://leetcode.com/problems/implement-trie-prefix-tree/description/

문자열을 저장하고 검색하는 Trie 클래스를 만드는 문제이다. 단순하게 List 클래스를 이용하여 해결해 주었다. insert 와 search의 경우 ArrayList 클래스의 기본 메서드를 이용해 주었으며
검색 시에는 리스트를 순회하며 substring 하여 prefix와 substring 한 결과를 비교해주었다.

public class Trie {  
  
    List<String> list;  
  
    public Trie() {  
        list = new ArrayList<>();  
    }  
  
    public void insert(String word) {  
        list.add(word);  
    }  
  
    public boolean search(String word) {  
        return list.contains(word);  
    }  
  
    public boolean startsWith(String prefix) {  
        for(int i = 0; i < list.size(); i++){  
            String str = list.get(i);  
            if(str.length() >= prefix.length()  
                    && str.substring(0, prefix.length()).equals(prefix)) return true;  
        }  
  
        return false;  
    }  
}  
  
/**  
 * 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); 
           */

https://leetcode.com/problems/combination-sum/description/

타겟의 합계를 맞추기 위해 알맞은 요소의 조합을 찾는 문제이다.
전형적인 DFS 백트래킹 문제로 조건들을 문제에 맞춰 해결 해주면 된다. 크게 특이사항은 없는 문제였다.

class Solution {  
  
    static int[] candidates;  
    static int target;  
    static List<List<Integer>> answer;  
  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {  
        this.candidates = candidates;  
        this.target = target;  
        this.answer = new ArrayList<>();  
        List<Integer> init = new ArrayList<Integer>();  
        for(int i = 0; i < candidates.length; i++){  
            init.add(candidates[i]);  
            dfs(0, i, init);  
            init.remove(0);  
        }  
  
        return answer;  
    }  
  
    private void dfs(int sum, int idx, List<Integer> list){  
        int curCandidate = candidates[idx];  
        sum += curCandidate;  
        if(sum == target){  
            answer.add(new ArrayList<>(list));  
            return;  
        }  
  
        // 중복 조합을 피하기위해 현재 idx보다 높은 경우만 체크  
        for(int i = idx; i < candidates.length; i++){  
            int nextCandidate = candidates[i];  
            if(nextCandidate + sum > target) continue;  
  
            list.add(nextCandidate);  
            int curListIdx = list.size() - 1;  
            dfs(sum, i, list);  
            list.remove(curListIdx);  
        }  
    }  
}

https://leetcode.com/problems/k-closest-points-to-origin/description/

원점에서 가까운 순서대로 좌표 k 개를 찾는 문제이다. 가까운 순서대로 정렬해야 하므로 PriorityQueue를 이용하여 해결하였다.

PriorityQueue를 이용할 때 원하는 방식으로 정렬하기 위해선 Comparator를 지정해주거나 class가 Comparable 인터페이스를 구현하면 된다. Point에 대하여 별도의 클래스를 생성했으므로 Comparable 인터페이스를 구현해주었다.

원점까지의 거리는 두 점의 차이점에 제곱을 각각 한 이후 루트를 해주어야 하지만, 원점의 좌표가 0인점, 그리고 루트 계산을 해주지 않아도 크기 비교는 할 수 있다는 점에서 루트 계산은 제거하였다.

import java.util.*;  
  
public class Solution {  
    public int[][] kClosest(int[][] points, int k) {  
  
        PriorityQueue<Point> pq = new PriorityQueue<>();  
  
        for(int i = 0; i < points.length; i++){  
            int x = points[i][0];  
            int y = points[i][1];  
            pq.add(new Point(x, y));  
        }  
  
        int[][] answer = new int[k][2];  
        while(k-- > 0){  
            Point point = pq.poll();  
            answer[k][0] = point.x;  
            answer[k][1] = point.y;  
        }  
  
        return answer;  
    }  
  
    private class Point implements Comparable<Point>{  
        int x;  
        int y;  
        int distFromOrigin;  
  
        Point(int x, int y){  
            this.x = x;  
            this.y = y;  
            this.distFromOrigin = x*x + y*y;  
        }  
  
        @Override  
        public int compareTo(Point o){  
            return this.distFromOrigin - o.distFromOrigin;  
        }  
    }  
}

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

트리의 깊이를 찾는 문제이다. 트리의 깊이를 찾기 위해 노드를 순차적으로 탐색해야 한다.
탐색하기 위해 Queue를 사용했으며, 노드를 Queue에 삽입할 때 현재의 깊이를 기준으로 1 추가하여 주었고, left 와 right가 null 이 아닌것을 체크하여 Queue에 삽입하고 poll하며 깊이를 확인해 주었다.

/**  
 * 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; 
 *     } 
 * } 
 */  
 
import java.util.*;  
  
public class Solution {  
    public int maxDepth(TreeNode root) {  
        if(root == null) return 0;  
  
        Queue<Depth> que = new ArrayDeque<>();  
        Depth rootDepth = new Depth(root, 1);  
        que.add(rootDepth);  
        int answer = 0;  
  
        while(!que.isEmpty()){  
            Depth curDepth = que.poll();  
            int depth = curDepth.depth;  
            TreeNode cur = curDepth.node;  
            answer = Math.max(depth, answer);  
  
            if(cur.left != null){  
                Depth nextLeftDepth = new Depth(cur.left, depth + 1);  
                que.add(nextLeftDepth);  
            }  
  
            if(cur.right != null){  
                Depth rightLeftDepth = new Depth(cur.right, depth + 1);  
                que.add(rightLeftDepth);  
            }  
        }  
  
        return answer;  
    }  
  
    private class Depth{  
        TreeNode node;  
        int depth;  
  
        Depth(TreeNode node, int depth){  
            this.node = node;  
            this.depth = depth;  
        }  
    }  
}

두 개의 LinkedList를 정렬하여 합치는 문제이다. leetcode에서 제공하는 커스텀 클래스이며, 생성자를 잘 이용해 주어야 한다.

두 개의 리스트를 차례대로 확인하는 방법도 있겠지만 편의성을 위해 PriorityQueue를 이용하여 문제를 해결해보았다. 두 리스트의 값을 전부 넣은 이후 순서대로 꺼내서 새로 이어 주었다.

/**  
 * 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; } * } */  
import java.util.*;  
  
class Solution {  
  
    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b.compareTo(a));  
  
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {  
        ListNode answer = null;  
        pqAddAllList(list1);  
        pqAddAllList(list2);  
        while(!pq.isEmpty()){  
            answer = new ListNode(pq.poll(), answer);  
        }  
  
        return answer;  
    }  
  
    private void pqAddAllList(ListNode list){  
        while(list != null){  
            pq.add(list.val);  
            list = list.next;  
        }  
    }  
}