꿀잠

https://leetcode.com/problems/set-matrix-zeroes/description/

주어진 매트릭스에서 0이 존재하는 행과 열을 0으로 전부 변환시키는 문제이다. 별도의 배열을 완성하는게 아니라 기존의 매트릭스를 변환해야한다. 특정 좌표의 (r, c)에 0이 존재하면 해당 r행과 c열을 모두 변환하기에 이를 체크하기 위해 boolean 배열로 체크했다. 아래는 통과코드이다.

  public class Solution {  
  
    public void setZeroes(int[][] matrix) {  
  
        int m = matrix.length;  
        int n = matrix[0].length;  
        boolean[] checkRow = new boolean[m];  
        boolean[] checkCol = new boolean[n];  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                if(matrix[i][j] == 0){  
                    checkRow[i] = true;  
                    checkCol[j] = true;  
                }  
            }  
        }  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                if(checkRow[i] || checkCol[j]){  
                    matrix[i][j] = 0;  
                }  
            }  
        }  
    }  
  
}

https://leetcode.com/problems/counting-bits/description/

bit의 개수를 새는 문제로 특정 숫자가 아니라 n까지의 모든 개수를 세는 문제이다. n이 충분히 크다면 속도가 굉장히 느려질 것을 예상해서 문제를 풀어야 할 것으로 추측할 수 있다. dp 방식으로 기존의 값에서 개수를 가져와야 빠르게 샐 수 있다. 이진수는 커질수록 자리수가 늘어난다는 점에서 착안하면 점화식을 세울 수 있다.

2, 3과 4의 이진수는 아래와 같다. 

2 - 10
3 - 101
4 - 100

3과 4는 2의 이진수에 1과 0이 추가된 형태이다. 2가 가진 1의 개수를 알 수 있다면 3의 경우 1개 추가된 것이고, 4의 경우 0개 추가되어 같은 것이다. 위와 같이 2와 3,4의 관계는 비트 이동 연산자를 통해 쉽게 찾을 수 있다. 3과 4의 비트를 오른쪽으로 한 칸 이동하면 되기 때문이다. 이와 같은 생각을 바탕으로 점화식을 세워 아래와 같이 풀 수 있다.

public class Solution {  
    public int[] countBits(int n) {  
        int[] ans = new int[n + 1];  
        for(int i = 0; i <=n; i++){  
            int cnt = 0;  
            ans[i] = ans[i >> 1] + (i & 1);  
        }  
  
        return ans;  
    }  
}

(start, end)로 이루어진 구간 배열에서 서로 겹치지 않는 구간들만 남기기 위하여 지워야 하는 최소 원소의 개수를 구하는 문제이다. 구간의 겹침은 2번 구간의 시작 점이 1번 구간의 끝 지점 앞에 있다면 겹친다고 할 수 있다. 그리고 두 구간이 겹친다면 범위가 더 좁을 수록 좋다고 할 수 있다

.

구간을 효율적으로 비교하기 위하여 시작 지점을 기반으로 정렬한 이후 현재 위치보다 뒤에 있는 배열을 비교하며 체크해 주었다. 아래는 통과한 코드이다.

import java.util.*;  
  
class Solution {  
    public int eraseOverlapIntervals(int[][] intervals) {  
        Arrays.sort(intervals, (a, b) -> {  
            return Integer.compare(a[0],b[0]);  
        });  
  
        int answer = 0;  
        boolean[] removed = new boolean[intervals.length];  
        for(int i = 0; i < intervals.length - 1; i++){  
            if(removed[i]) continue;  
  
            int[] itv1 = intervals[i];  
            for(int j = i + 1; j < intervals.length; j++){  
                if(removed[j]) continue;  
  
                int[] itv2 = intervals[j];  
                if(itv2[0] < itv1[1]){  
                    answer++;  
                    if(itv1[1] > itv2[1]){  
                        removed[i] = true;  
                        break;  
                    }  
                    removed[j] = true;  
                }  
            }  
        }  
  
        return answer;  
    }  
}

하지만 이보다 더 효율적인 속도가 나오는 코드들이 있어 확인했다. 내가 해결한 코드의 경우 제거한 이후에는 removed 배열을 만들어 체크해주며 중복 체크를 피하고 있었다.

하지만 더 효율적인 속도의 코드의 경우 한번의 for문으로 해결하고 있었다. 각 요소를 한번만 체크하고 바로 제거할 것을 확인한 이후 다음 요소로 건너가는 방법이었다. 이 때 비교 군은 변수에 저장하여 유지하는 방식이었다. 그 방법은 아래와 같다.

```java
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        
        Arrays.sort(intervals , (a,b) -> a[0]-b[0]);
        int s1 = intervals[0][0];
        int e1 = intervals[0][1];
        int cnt = 0;

        for(int i=1;i<intervals.length;i++){

            int s2 = intervals[i][0];
            int e2 = intervals[i][1];

            if(e1 > s2){
                cnt++;
                s1 = s1;
                e1 = Math.min(e1,e2);
                continue;
            }

            s1 = s2;
            e1 = e2;
        }
        return cnt;
    }
}

https://leetcode.com/problems/gas-station/description/

각 지역으로 이동을 위해 가스를 사용하고 충전하는 경우에 전체 지역을 한 바퀴 가능한지 확인하는 문제이다.

전체를 이동 가능한 지역은 하나로 유니크하며, 불가능할 경우 판단하여 -1을 리턴해야한다. 기본적으로 전체 지역을 완주하기 위해선 전체 가스의 총량이 전체 이동 코스트보다 낮아야 한다.

그렇기 때문에 0번 지역에서 부터 마지막 지역까지 확인하며 가스가 부족해지지 않는 시작 지점을 찾고, 완주할 전체 가스량이 된다면 이동이 가능하다는 것을 알 수 있다. 이러한 그리디 알고리즘으로 해결한 코드이다.

public class Solution {  
    public int canCompleteCircuit(int[] gas, int[] cost) {  
        int sum = 0;  
        int start = 0;  
        int total = 0;  
        for(int i = 0; i < gas.length; i++){  
            sum += gas[i] - cost[i];  
            if(sum < 0){  
                total += sum;  
                start = i + 1;  
                sum = 0;  
            }  
        }  
  
        total += sum;  
  
        return total >= 0  ? start : -1;  
    }  
  
}

https://leetcode.com/problems/edit-distance/

이번 문제는 DP 문제로 1번 문자열을 2번 문자열로 변환 시킬 때 삽입,삭제,대체 의 세가지 기능을 이용하여 최소 몇 번으로 변화 시킬 수 있는지 묻는 문제이다. DP 문제라는 것을 알고도 아이디어가 떠오르지 않아 한참 고민하다 결국 정답 영상을 찾아 보고야 말았다. 정답을 확인하고 나니 이전에 풀었던 최대 부분 문자열 찾기 문제랑 흡사한 형태였다. 해당 문제는 아래에 있다.

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

이 문제를 풀이 이해하기 위해선 DP 배열 표를 만들어 보면 이해하기 쉽다. 문제에 주어진 예제중 하나인 horse 와 ros 를 기준으로 예외 표를 아래와 같이 그릴 수 있다.

각 좌표에서의 값을 분석해보자 우선 1행과 1열의 값을 보자.
빈 문자열에서 h, ho, hor, hors, hosrse 의 문자열을 만들기 위해선 삽입이란 행동이 필요하므로 1씩 증가한다. 마찬가지의 원리로 1열 또한 증가한다. 임의의 행, 열에서 각각의 행 문자와 열 문자가 같다면 i - 1, j - 1의 값과 같다. 예를 들어 hors 와 ros 의 최소 변환 값은 hor과 ro의 변환 값과 같다. 마지막 s는 변환이 필요 없기 때문이다. 따라서 i - 1, j - 1인 hor, ro의 값과 같다는 점을 알 수 있다.

한편 행과 열의 추가 문자가 다른 경우를 보자 ho와 r의 경우 2이다. 이 경우는 h, r 에서 o를 삭제하는 행위가 추가되는 경우이고, , h,""의 경우의 수에 o를 r로 대체하는 경우의 수가 추가되는 경우이다. 이처럼 i - 1의 경우 삽입의 경우의 수가 늘어나고, j - 1 의 경우 삭제의 경우의 수가 늘어나는 경우, 그리고 i - 1, j - 1 의 경우 대체의 경우의 수가 늘어나는 경우이다.

특정 i, j 에서 글자 수가 생성된다면 이 경우의 수에 한 번의 삽입, 삭제, 대체로 변환 시킬 수 있다. 따라서 최소 변환 방법은 (i, i - 1), (j, j - 1), (i - 1, j - 1)의 값 중에서 가장 작은 값에 1을 추가 시킨 경우이다. 이를 이용하여 점화 식을 만들어 해결하면 아래와 같은 코드가 나온다.

 public class Solution {  
    public int minDistance(String word1, String word2) {  
        int m = word1.length() + 1;  
        int n = word2.length() + 1;  
  
        int[][] dp = new int[m][n];  
  
        for(int i = 0; i < m; i++){  
            dp[i][0] = i;  
        }  
  
        for(int j = 0; j < n; j++){  
            dp[0][j] = j;  
        }  
  
        for(int i = 1; i < m; i++){  
            char c1 = word1.charAt(i - 1);  
            for(int j = 1; j < n; j++){  
                char c2 = word2.charAt(j - 1);  
                if(c1 == c2){  
                    dp[i][j] = dp[i - 1][j - 1];  
                }else{  
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;  
                }  
            }  
        }  
  
        return dp[m - 1][n - 1];  
    }  
}

https://leetcode.com/problems/coin-change/description/

주어진 코인 종류로 목표 금액을 맞추기 위해 필요한 최소 개수를 구하는 문제이다. dp 문제로 어떻게 풀어낼지 고민하다가 에라토스테네스의 체 알고리즘이 떠올랐다. 해당 알고리즘은 소수를 구하는 알고리즘으로 소수들로 이루어질 수 있는 약수들을 하나씩 체에 거르는 식으로 지워가는 방법이다.

그와 마찬가지로 이 문제의 경우 코인의 종류 별로 이룰 수 있는 값들의 최소 개수를 dp 배열에 적어가며 업데이트 하며 문제를 해결해 나갔다. 작은 값부터 하여 dp[0]은 0인 값으로 코인 1개일 때의 값을 적절히 계산될 수 있도록 초기화 해준 이후 조건에서 제시한 최대 값을 기준으로 극한 값을 설정해주었다. 아래는 최종 코드이다.

import java.util.Arrays;  
  
public class Solution {  
    public int coinChange(int[] coins, int amount) {  
        Arrays.sort(coins);  
  
        int[] dp = new int[amount + 1];  
        int INF = 10001;  
        Arrays.fill(dp, INF);  
        dp[0] = 0;  
  
        for (int i = 0; i < coins.length; i++) {  
            int coin = coins[i];  
            for (int j = coin; j <= amount; j++) {  
                dp[j] = Math.min(dp[j - coin] + 1, dp[j]);  
            }  
        }  
  
  
        return dp[amount] == INF ? -1 : dp[amount];  
    }  
}

https://leetcode.com/problems/cheapest-flights-within-k-stops/

정해진 경유지 수 이내에서 목적지까지 가장 적은 비용으로 도달하는 방법을 찾는 문제이다.
목적지까지 최단 비용 문제의 경우 다익스트라 알고리즘을 이용해줄 수 있다.

해당 문제 또한 다익스트라 알고리즘으로 해결할 수 있으며, 특이점으로는 경유지 숫자에 제한이 있다는 점이다. 따라서 PriorityQueue를 이용하여 경로를 설정할 때 경유지 개수를 포함 시켜 문제를 해결하였다.

public class Solution {  
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {  
        List<Route>[] prices = new ArrayList[n];  
        for(int i = 0; i < n; i++){  
            prices[i] = new ArrayList<>();  
        }  
  
        PriorityQueue<Route> pq = new PriorityQueue<>((a, b) -> {  
            if(a.stop == b.stop){  
                return a.price - b.price;  
            }  
            return a.stop - b.stop;  
        });  
  
        for(int[] flight: flights){  
            int from = flight[0];  
            int to = flight[1];  
            int price = flight[2];  
  
            prices[from].add(new Route(to, price, 0));  
        }  
  
        for(Route route: prices[src]){  
            pq.add(route);  
        }  
  
        int[] minValue = new int[n];  
        Arrays.fill(minValue, Integer.MAX_VALUE);  
        while(!pq.isEmpty()){  
            Route now = pq.poll();  
            int to = now.to;  
            int price = now.price;  
            int stop = now.stop;  
            if(k < stop){  
                continue;  
            }  
  
            if(minValue[to] < price){  
                continue;  
            }  
  
            minValue[to] = price;  
  
            for(Route next: prices[to]){  
                int nextTo = next.to;  
                int nextPrice = price + next.price;  
                int nextStop = stop + 1;  
                if(minValue[nextTo] > nextPrice){  
                    pq.add(new Route(nextTo, nextPrice, nextStop));  
                }  
            }  
        }  
  
        return minValue[dst] == Integer.MAX_VALUE ? -1 : minValue[dst];  
    }  
  
    private class Route{  
        int to;  
        int price;  
        int stop;  
  
        Route(int to, int price, int stop){  
            this.to = to;  
            this.price = price;  
            this.stop = stop;  
        }  
    }  
}

https://leetcode.com/problems/pacific-atlantic-water-flow/description/

주어진 좌표가 두 가지 해역으로 둘러 쌓여있고, 높이 값일 때 높은 곳에서 낮은 곳으로 홍수로 인해 물이 흐른다. 이 때 양쪽 해역으로 물이 다 흐르는 좌표를 찾는 문제이다.

물이 흐를 수 있다는 것은 각 해변 좌표 쪽까지 도달할 수 있다는 것이다. 그렇기 때문에 역으로 해변 쪽 좌표에서 높아 지는 좌표들을 체크한다면 정답 좌표들을 찾아 나갈 수 있다. 이 때 해역이 두 가지 이므로 visited 배열을 두 가지 사용한 이후 두 visited 모두를 확인하여 정답 목록을 체크할 수 있다. bfs방식으로 그래프를 탐색했으면 완성 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> pacificAtlantic(int[][] heights) {  
        int m = heights.length;  
        int n = heights[0].length;  
        boolean[][] pacific = new boolean[m][n];  
        boolean[][] atlantic = new boolean[m][n];  
        List<List<Integer>> answer = new ArrayList<>();  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                // pacific,북쪽  
                if(i == 0){  
                    bfs(i, j, heights, pacific);  
                // pacific,서쪽  
                }else if(j == 0){  
                    bfs(i, j, heights, pacific);  
                }  
  
                // atlantic,동쪽  
                if(i == m - 1){  
                    bfs(i, j, heights, atlantic);  
                // atlantic,남쪽  
                }else if(j == n - 1){  
                    bfs(i, j, heights, atlantic);  
                }  
            }  
        }  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j <n; j++){  
                if(pacific[i][j] && atlantic[i][j]) answer.add(List.of(i, j));  
            }  
        }  
  
        return answer;  
    }  
  
    private void bfs(int r, int c, int[][] heights, boolean[][] visited){  
        int[] dr = {-1,0,1,0};  
        int[] dc = {0,-1,0,1};  
  
        Queue<int[]> que = new ArrayDeque<>();  
        que.add(new int[]{r, c});  
  
        while(!que.isEmpty()){  
            int[] now = que.poll();  
            int row = now[0];  
            int col = now[1];  
            if(visited[row][col]){  
                continue;  
            }  
  
            visited[row][col] = true;  
  
            for(int dir = 0; dir < 4; dir++){  
                int nextRow = row + dr[dir];  
                int nextCol = col + dc[dir];  
  
                if(nextRow >= 0 && nextRow < heights.length  
                        && nextCol >= 0 && nextCol < heights[0].length  
                        && !visited[nextRow][nextCol]  
                        && heights[nextRow][nextCol] >= heights[row][col]){  
                    que.add(new int[]{nextRow, nextCol});  
                }  
            }  
  
        }  
    }  
  
}