꿀잠

https://leetcode.com/problems/jump-game/

0번 인덱스부터 최종 인덱스까지 각 인덱스에서의 nums[i] 수치만큼 이동할 수 있을때 끝까지 도달할 수 있는지에 대한 문제이다.

최종 목표지에 도달하기 위해선 특정 인덱스에서의 점프력(값이) 마지막 인덱스보다 높아야 한다.

그리고 해당 인덱스 까지 도달하기 위해서는 그 이전에서 점프력이 넘어야한다.

이를 반복해서 최초 시작 지점에서 목표 지점까지 뛸 수 있다면 가능하다고 할 수 있다.

배열을 역으로 내려오면 확인하며 풀었다.

public class Solution {  
    public boolean canJump(int[] nums) {  
        int goal = nums.length - 1;  
  
        for(int i = nums.length - 1; i >= 0; i--){  
            int num = nums[i];  
            if(i + num >= goal){  
                goal = i;  
            }  
        }  
  
        return goal == 0;  
    }  
}

https://leetcode.com/problems/climbing-stairs/description/

계단을 1, 2 단씩 오를수 있을때 n계의 계단을 오르는 방법의 개수를 묻는 DP 문제이다.
n번재 계단을 오르기 위해선 n-1 번째에서 한 걸음, n-2 에서 두 걸음 오르는 방법이 있으므로

해당 방식으로 dp 점화식을 만들어 문제를 해결하였다.

public class Solution {  
    public int climbStairs(int n) {  
        int[] dp = new int[46];  
        dp[0] = 0;  
        dp[1] = 1;  
        dp[2] = 2;  
  
        for(int i = 3; i <= n; i++){  
            dp[i] = dp[i - 2] + dp[i - 1];  
        }  
  
        return dp[n];  
    }  
}

https://leetcode.com/problems/network-delay-time/description/

주어진 노드로 부터 최단 경로를 묻는 다익스트라 알고리즘을 사용하는 문제였다.
예전에 공부했었는데 잘 기억이 나지 않아 복습하며 풀었다. 처음에 오래된 기억으로 더듬 거리며 풀다보니 시간 초과가 나왔다. 복습하며 잘못된 부분들을 해결 하며 풀었다.

다익스트라는 주어진 시작점으로 부터 최단 경로를 기준으로 경로를 이어 나가는 그리디 + DP 형식의 그래프 문제이다. 최단경로를 이어나가기 위해 PriorityQueue 사용했으며, 각 경로의 최소 길이를 배열에 저장하여 DP 배열로 활용하였다.

import java.util.*;  
  
public class Solution {  
    public int networkDelayTime(int[][] times, int n, int k) {  
  
        // node 정보를 담을 List 초기화  
        List<Node>[] nodes = new List[n + 1];  
        for(int i = 0; i < nodes.length; i++){  
            nodes[i] = new ArrayList<>();  
        }  
  
        for(int[] time: times){  
            int from = time[0];  
            int to = time[1];  
            int travel = time[2];  
            // node 정보 List에 담기  
            nodes[from].add(new Node(to, travel));  
        }  
  
        // 다익스트라 알고리즘을 사용하기 위한 pq        
        // 최단경로를 저장하기 위한 travels        
        PriorityQueue<Node> pq = new PriorityQueue<>();  
        int[] travels = new int[n + 1];  
  
        // 최단경로 무한대로 초기화  
        for(int i = 1; i < travels.length; i++){  
            travels[i] = Integer.MAX_VALUE;  
        }  
  
        // 시작지점 처리  
        travels[k] = 0;  
        pq.add(new Node(k, 0));  
  
        while(!pq.isEmpty()){  
            Node cur = pq.poll();  
  
            // 현재 지점까지 최단 경로인지 확인, visited 체크 역할  
            if (cur.travel > travels[cur.node]){  
                continue;  
            }  
  
            // 다음 경로 확인  
            for (Node next : nodes[cur.node]) {  
                int newTravel = cur.travel + next.travel;  
                // 다음 경로중 최단경로인 경우 pq 경로 추가  
                if (newTravel < travels[next.node]) {  
                    travels[next.node] = newTravel;  
                    pq.add(new Node(next.node, newTravel));  
                }  
            }  
        }  
  
        int answer = 0;  
        for(int i = 1; i < travels.length; i++){  
            // 가장 오래 걸린 경우 Network Delay를 마친 시간  
            answer = Math.max(travels[i], answer);  
        }  
  
        // 도달하지 못한경우 초기 거리값을 가지고 있으므로 -1, 아니면 answerreturn answer == Integer.MAX_VALUE ? -1 : answer;  
    }  
  
    private static class Node implements Comparable<Node>{  
        int node;  
        int travel;  
  
        Node(int node, int travel){  
            this.node = node;  
            this.travel = travel;  
        }  
  
        @Override  
        public int compareTo(Node o){  
            return Integer.compare(this.travel, o.travel);  
        }  
    }  
}

https://leetcode.com/problems/number-of-islands/description/

주어진 그리드에서 땅으로 연결된 섬이 몇 개인지 체크하는 문제이다.
bfs를 이용하여 땅인 부분 확인하고 섬의 개수를 확인하였으며, 이때 땅을 확인할 때 bfs를 이용하여 연결된 모든 땅을 CHECK_LAND로 변경하여 연결된 땅을 샐 수 있도록 하였다.

import java.util.*;  
  
public class Solution {  
  
    private static final char LAND = '1';  
    private static final char WATER = '0';  
    private static final char CHECK_LAND = '3';  
  
    public int numIslands(char[][] grid) {  
        int cnt = 0;  
  
        for (int i = 0; i < grid.length; i++) {  
            for (int j = 0; j < grid[0].length; j++) {  
                if (bfs(i, j, grid)) {  
                    cnt++;  
                }  
                ;  
            }  
        }  
  
        return cnt;  
    }  
  
    private boolean bfs(int row, int col, char[][] grid) {  
        // 현재 좌표가 땅인지 확인  
        if (grid[row][col] != LAND) {  
            return false;  
        }  
  
        // 땅일 경우 최종적으로 true return, return 이전에 연결된 땅을  
        // bfs로 CHECK_LAND로 바꾸어 둔다. 연결된 땅은 땅으로 확인되지 않으므로  
        // 연결된 땅 전체를 하나로 확인 가능하다.  
        grid[row][col] = CHECK_LAND;  
  
        // 아래, 좌, 위, 우 각 방향 별로 확인하기 위한 방향 배열  
        int[] dr = {-1, 0, 1, 0};  
        int[] dc = {0, -1, 0, 1};  
  
        // que 에 넣기 위해 Pos class를 만들어서 이용, int[] 을 사용해도 무방하다.  
        Queue<Pos> que = new ArrayDeque<>();  
        que.add(new Pos(row, col));  
  
        while (!que.isEmpty()) {  
            Pos cur = que.poll();  
            for (int i = 0; i < 4; i++) {  
                int nextr = cur.r + dr[i];  
                int nextc = cur.c + dc[i];  
  
                // 그리드 범위조건, 땅인 부분의 경우 CHECK로 변환  
                if (nextr >= 0  
                        && nextr < grid.length  
                        && nextc >= 0  
                        && nextc < grid[0].length  
                        && grid[nextr][nextc] == LAND  
                ) {  
                    grid[nextr][nextc] = CHECK_LAND;  
                    que.add(new Pos(nextr, nextc));  
                }  
            }  
        }  
  
        return true;  
    }  
  
    private class Pos {  
        int r;  
        int c;  
  
        Pos(int r, int c) {  
            this.r = r;  
            this.c = c;  
        }  
    }  
}

연결된 땅을 하나씩 샐 수 있도록 bfs 를 이용하여 푼 문제였다, 각 방향으로 bfs 그래프를 탐색하며, 그리드의 범위, 땅인지 아닌지를 체크할 때 조건을 잘 확인해야한다.

https://leetcode.com/problems/subsets/description/

주어진 배열의 모든 subset을 List로 리턴하는 문제이다.
각 요소를 순회하기 위하여 dfs로 백트래킹을 하여 가능하며, 중복 요소를 제거하기 위하여
현재 인덱스 이후 기준으로 dfs 탐색 하였다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> subsets(int[] nums) {  
        List<List<Integer>> answer = new ArrayList<>();  
        List<Integer> cur = new ArrayList<>();  
        boolean[] visited = new boolean[nums.length];  
        dfs(answer, cur, -1, visited, nums);  
  
        return answer;  
    }  
  
    private void dfs(List<List<Integer>> answer, List<Integer> cur, int curidx, boolean[] visited, int[] nums){  
        // Array 의 값을 복사하여 넣어준다.  
        List<Integer> subset = new ArrayList<>(cur);  
        answer.add(subset);  
  
        for(int i = curidx + 1; i < visited.length; i++){  
            if(!visited[i]){  
                cur.add(nums[i]);  
                int curSize = cur.size();  
                visited[i] = true;  
                dfs(answer, cur, i, visited, nums);  
                // 값을 다시 초기화하여 백트래킹 한다.  
                visited[i] = false;  
                cur.remove(curSize - 1);  
            }  
        }  
    }  
}

서브 셋을 추가할 땐 해당 배열을 복사해서 추가해주었다.

List의 참조 값을 바라보므로 해당 시점의 배열 요소로 복사해서 넣어주어야 한다.

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

sort를 쓰지 않고 배열의 K번째로 큰 요소를 찾는 문제이다.
알고리즘을 복습하려고 따라가고 있는 리트코드 로드맵상에선 Heap & Priority Queue로 지정되어있어 Priority Queue를 이용해서 풀었다.

사실 PriorityQueue도 sort를 이용하는게 아닌가 하는 의구심이 들기는 한다.
하지만 Arrays.sort()를 이용하여 문제를 풀 경우 오류를 내뱉었다.

문제에서 PriorityQueue를 사용시 오류가 발생하지 않으며 이는 PriorityQueue를 허용한다는 의미이며

그것이 문제의 의도라고 확인하였다.
문제 풀이에 성공한 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int findKthLargest(int[] nums, int k) {  
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);  
        // PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  
        for (int num : nums) {  
            pq.add(num);  
        }  
  
        while (k-- > 1) {  
            pq.poll();  
        }  
  
        return pq.poll();  
    }  
}

PriorityQueue 는 기본적으로 Integer 의 compareTo 메서드에 따라 오름차순으로 정렬하기 때문에 생성시 새로운 compareTo 메서드를 오버라이드 해야한다. Collections.reverseOrder()를 이용해 간단히 역순 정렬을 할 수도 있으며, 직접 수식을 compareTo 메서드에 오버라이드 해주는 것도 방법이다. 이 때 화살표 함수로 손쉽게 메서드를 표기할 수 있다.

PriorityQueue에 nums 배열을 넣은 후에는 간단하다. k번째로 큰수이기 때문에 k번째의 수를 뽑아내주면 된다. k-1 번째까지 뽑은 후 리턴시 k번째 수를 poll하여 반환하였다.

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

주어진 커스텀 클래스인 이진트리 노드를 레벨에 따른 중첩 List배열로 반환하는 문제이다.

/**
 * 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<List<Integer>> levelOrder(TreeNode root) {  
        List<List<Integer>> answer = new ArrayList<>();  
        if (root == null) {  
            return answer;  
        }  
  
        Queue<TreeNode> que = new ArrayDeque<>();  
        que.offer(root);  
  
        while (!que.isEmpty()) {  
            List<Integer> levelList = new ArrayList<>();  
            int queSize = que.size();  
  
            while (queSize-- > 0) {  
                TreeNode node = que.poll();  
                levelList.add(node.val);  
                if (node.left != null) {  
                    que.offer(node.left);  
                }  
  
                if (node.right != null) {  
                    que.offer(node.right);  
                }  
            }  
            if (levelList.size() > 0) {  
                answer.add(levelList);  
            }  
        }  
  
        return answer;  
    }
}

레벨 단위로 처리하기 위해서 Queue를 이용하였다. 하나의 레벨을 Queue 에 넣어 전부 꺼내며 리스트를 완성하고, 전부 꺼내는 동안 다음 레벨의 노드를 Queue에 넣어 순차적으로 레벨 List를 만들어 주었다. 하나의 레벨을 꺼내며 Queue에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.