꿀잠

https://leetcode.com/problems/spiral-matrix/

주어진 매트릭스를 주어진 방식으로 안으로 순회하며 값을 리스트에 담아 리턴하는 문제이다.
행과 열의 방향을 배열로 하여 돌아갈 방향을 정해줄 수 있다.

    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    
    int dir = 0;
    int nextRow = curRow + dr[dir];
    int nextCol = curCol + dc[dir]; 

위와 같은 형식으로 dir의 값 0~3에 따라 다음 좌표의 행과 열을 이동할 수 있다. dr, dc 의 인덱스별 값에 따라 위치를 지정해줄 수 있으며 문제에서 주어진 방식으로 순서대로 회전하기 위해서 위 코드와 같은 순서로 배열의 값을 지정해주었다.

그 이후 회전하는 타이밍을 정해야 했다. 회전하는 타이밍은 벽에 막히거나 또는 다음 위치가 이미 방문할 위치일 경우이다. 이를 위해서 매트릭스의 범위와 visited 배열을 이용하여 체크해주었다. 아래는 해결한 전체 코드이다.

import java.util.*;  
  
public class Solution {  
  
    static int[] dr = {0, 1, 0, -1};  
    static int[] dc = {1, 0, -1, 0};  
    static boolean[][] visited;  
  
    public List<Integer> spiralOrder(int[][] matrix) {  
        List<Integer> answer = new ArrayList<>();  
  
        visited = new boolean[matrix.length][matrix[0].length];  
  
        int r = 0;  
        int c = 0;  
        int dir = 0;  
  
        while(isValidDirection(matrix, r, c)){  
            visited[r][c] = true;  
  
            answer.add(matrix[r][c]);  
            int nextr = r + dr[dir];  
            int nextc = c + dc[dir];  
            if(!isValidDirection(matrix, nextr, nextc)){  
                dir = (dir + 1) % 4; // 0 - 우, 1 - 하, 2 - 좌, 3 - 상  
                nextr = r + dr[dir];  
                nextc = c + dc[dir];  
            }  
  
            r = nextr;  
            c = nextc;  
        }  
  
        return answer;  
    }  
  
    private boolean isValidDirection(int[][] matrix, int r, int c){  
        return r >= 0 && r < matrix.length  
                && c >= 0 && c < matrix[0].length  
                && !visited[r][c];  
    }  
}

주어진 양수의 비트의 값이 1의 개수를 세는 문제이다. 최초 해결 후 비트연산자 학습을 위해 추가로 해결해보았으며 총 3가지 방법으로 해결해보았다.

1. 일단 주어진 자연수를 2진수로 변환하여 문자열에서 '1'의 개수를 세는 방법으로 해결하였다.
2. 하지만 비트 조작의 카테고리에 맞춰 풀기 위해 비트 이동 연산자와 '&' 논리 연산자를 이용하여 해결해보았다.
3. 관련해서 비트 연산자를 공부하던 중 Java 의 경우는 개수를 세어주는 Integer 메서드 bitCount 가 있다는 사실도 알았다. 해당 메서드를 이용해서도 바로 문제가 해결된다.

아래 코드는 세가지 모두 적어두었다.

public class Solution {  
    public int hammingWeight(int n) {  
    
        // 1. 문자열 이용  
        // String s = Integer.toString(n, 2);  
        // int answer = 0;        
        // for(char c: s.toCharArray()){        
        //     if(c == '1') answer++;        
        // }        
        // return answer; 
         
         
        // 2. 비트연산자 이용  
        // int answer = 0;  
        // while(n != 0){        
        //     if((n & 1) == 1) answer++;        
        //     n = n >> 1;        
        // }        
        // return answer;  
        
        
        // 3. Java Integer 메서드 이용  
        return Integer.bitCount(n);  
    }  
}

https://leetcode.com/problems/insert-interval/description/

이전에 풀었던 Merge Intervals 문제와 거의 같은 문제이다. 단 두번째 매개변수로 하나의 Intervals를 추가해주어야 한다. 이전에 풀었던 방식에서 PriorityQueue에 신규 Intervals 만 추가해 주면 문제를 해결할 수 있었다. 이전에 풀었던 Merge Intervals는 아래와 같다.

https://blog.honey-sleep.co.kr/61

최종 코드는 아래와 같다.

public class Solution {  
    public int[][] insert(int[][] intervals, int[] newInterval) {  
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0] );  
        for(int[] interval:intervals){  
            pq.add(interval);  
        }  
        pq.add(newInterval); // newInterval 을 넣어준다.  
  
        List<int[]> newArray = new ArrayList<>();  
  
        while(!pq.isEmpty()){  
            int[] cur = pq.poll();  
            while(!pq.isEmpty() && pq.peek()[0] <= cur[1]){  
                int[] next = pq.poll();  
                cur[1] = Math.max(next[1], cur[1]);  
            }  
            newArray.add(cur);  
        }  
  
        int finalSize = newArray.size();  
        int[][] answer = new int[finalSize][2];  
  
        for(int i = 0; i < finalSize; i++){  
            answer[i][0] = newArray.get(i)[0];  
            answer[i][1] = newArray.get(i)[1];  
        }  
  
        return answer;  
    }  
}

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

다음 인덱스까지 배열의 현재 값만큼 점프할 수 있을 때 몇번의 스텝으로 최종위치에 도달할 수 있는지에 대한 문제이다. 현재 점프할 수 있는 위치에서 점프 가능한 곳의 최소 값을 dp 배열에 저장하여 해결하였다.

import java.util.*;  
  
public class Solution {  
    public int jump(int[] nums) {  
        int n = nums.length;  
        int[] dp = new int[n];  
        Arrays.fill(dp, Integer.MAX_VALUE);  
        dp[0] = 0;  
  
        for(int i = 0; i < n; i++){  
            int jump = nums[i];  
            int step = dp[i] + 1;  
            int jumpMax = Math.min(i + jump, n - 1);  
            for(int j = i; j <= jumpMax; j++){  
                dp[j] = Math.min(dp[j], step);  
            }  
        }  
  
        return dp[n - 1];  
    }  
}

하지만 이 문제는 그리디 카테고리에 있는 알고리즘 문제이기에 그리디 방식으로 푸는 방식이 궁금해졌다. 다른 솔루션을 찾아 보니 그리디 방식의 경우 핵심 아이디어는 점프한 곳에서 다음 점프 시 가장 먼 곳으로 점프할 수 있는 곳 인지이다. 가장 먼 곳으로 점프하는 경우는 그 이전 구간도 전부 점프할 수 있으므로 점프 가능성을 최선의 선택으로 고르는 그리디 알고리즘이었다. 확인한 솔루션은 아래와 같다.

class Solution {  
    public int jump(int[] nums) {  
        return stepsToJumpFrom(nums, 0);  
    }  
  
    private int stepsToJumpFrom(int[] nums, int start) {  
        if (start >= nums.length - 1) {  
            return 0;  
        }  
        if (start + nums[start] >= nums.length - 1) {  
            return 1;  
        }  
        int furthestReachableNext = -1;  
        int nextStart = start;  
        for (int i = start + 1; i <= start + nums[start]; i++) {  
            if (i + nums[i] > furthestReachableNext) {  
                furthestReachableNext = i + nums[i];  
                nextStart = i;  
                if (furthestReachableNext >= nums.length - 1) {  
                    break;  
                }  
            }  
        }  
        return stepsToJumpFrom(nums, nextStart) + 1;  
  
    }  
}

https://leetcode.com/problems/longest-common-subsequence/description/

두 문자열의 가장 긴 부분 문자열의 길이를 구하는 문제이다. 부분 문자열이란 말의 개념이 처음에는 혼돈이 와서 정답을 제출하면서 테스트 케이스들을 확인하고 진행하였다.

부분 문자열이란 두 전체 문자열을 이루는 문자들의 순서와 구성이 동일한 문자열을 말한다. 단 이때 전체 문자열에서 다른 문자가 있더라도 순서만 맞으면 된다.

1."ascne"
2."abdcet"

위의 두 문자가 있다면 최대 길이 부분 문자열은 "ace" 이다 ace 는 두 문자열을 이루는 문자에 순서대로 들어가며, 양쪽에 다 포함되기 때문이다.

문제를 이해하고 나서 풀이 방식이 떠오르지 않았지만 알고리즘 카테고리가 DP라는 것을 인지하고 나서는 풀이를 진행할 수 있었다. 만약 카테고리가 없었다면 혼자 풀기는 힘들었을 것 같다. 점화식의 아이디어는 두 문자열을 비교하는 것으로 시작한다.

1. 특정 인덱스의 두 문자열을 비교했을 때 두 문자열이 같다.
   ->두 문자열의 현재 인덱스 -1일 때의 최대 부분 문자열의 크기에서 1증가
2. 특정 인덱스의 두 문자열을 비교했을 때 두 문자열이 같다
   -> 두 문자열 인덱스 -1일 때 비교했을 때랑 최대 부분 문자열의 크기와 같음

인덱스 - 1 의 값을 처리해야 하므로 dp 배열의 크기를 +1 해주고 문자를 추출할 때는 -1 해서 문제를 해결해주었다. dp 배열의 마지막 행열 값이 문자열의 모든 문자를 확인한 값으로 최종 정답이 된다.

public class Solution {  
    public int longestCommonSubsequence(String text1, String text2) {  
  
        int text1Length = text1.length();  
        int text2Length = text2.length();  
  
        int[][] dp = new int[text1Length + 1][text2Length + 1];  
  
        for(int i = 1; i <= text1Length; i++){  
            char c1 = text1.charAt(i - 1);  
            for(int j = 1; j <= text2Length; j++){  
                char c2 = text2.charAt(j - 1);  
                if(c2 == c1){  
                    dp[i][j] = dp[i][j] = dp[i-1][j-1] + 1;  
                }else{  
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);  
                }  
            }  
        }  
  
        return dp[text1Length][text2Length];  
    }  
}

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