꿀잠

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

주어진 인트의 32비트 2진수 값을 순서를 반전 하였을 때 값을 리턴하는 문제이다.
StringBuilder 클래스의 reverse 메서드를 통해 문자열을 반전하기 쉬워 해당 메서드를 이용하여 해결하였다.

public class Solution {  
    public int reverseBits(int n) {  
        String from = Integer.toString(n, 2);  
        StringBuilder sb = new StringBuilder(from);  
        sb.reverse();  
  
        int needZero = 32 - sb.length();  
        for(int i = 0; i < needZero; i++){  
            sb.append('0');  
        }  
  
        return Integer.valueOf(sb.toString(), 2);  
    }  
}

비트 연산자를 이용해 해결하고 싶다면 아래와 같은 방식으로 해결할 수 있다.

class Solution {
    public int reverseBits(int n) {
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1;
        }
        
        return result;
    }
}

https://leetcode.com/problems/partition-labels/

같은 문자들은 한 구간으로 묶어 해당 구간들의 크기를 리턴하는 문제이다. 아이디어가 떠올라 쉬운 편인 문제였다. 현재 구간의 가장 마지막 끝은 구간 내의 모든 문자들을 포함 해야 하므로, 가장 큰 lastIndex의 값을 체크하면서 갱신하면 구간을 찾을 수 있다.

자바의 경우 String 클래스의 lastIndexOf 메서드를 통해 마지막 인덱스를 쉽게 찾을 수 있으므로 해당 메서드를 활용해서 문제를 해결해 주었다.

import java.util.*;  
  
public class Solution {  
    public List<Integer> partitionLabels(String s) {  
        List<Integer> answer = new ArrayList<>();  
  
        for(int i = 0; i < s.length(); i++){  
            int lastIdx = s.lastIndexOf(s.charAt(i));  
            int now = i;  
            while(now++ < lastIdx){  
                lastIdx = Math.max(lastIdx, s.lastIndexOf(s.charAt(now)));  
            }  
  
            answer.add(lastIdx - i + 1);  
            i = now - 1;  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/burst-balloons/description/

풍선을 터트리는 순서에 따라 얻는 점수가 다를 때 가장 크게 점수를 얻을 수 있는 방법에 대해 묻는 문제이다. DP 문제로 아이디어를 열심히 생각해 보았지만 잘 떠오르지 않아 해당 문제의 팁을 찾아보고 통과할 수 있었다.

풍선을 터트렸을 때 얻는 점수는 양쪽 좌우 잔여 풍선이 어떤지에 따라 다르다. 이 문제의 점화식의 아이디어는 특정 풍선을 터트릴 때 좌우로 구간이 나뉘며 문제를 작게 볼 수 있다는 점이다.

1 2 3 4 5 의 풍선이 있을 때 3을 터트릴 경우
1 2 - 3 - 4 5 문제를 3구간으로 나눌 수 있다.
1 2 구간의 최대 가능 점수, 3을 터트렸을 때의 점수, 4 5 구간의 최대 가능 점수이다.

이러한 사실을 이용해서 점화식을 세우고, 큰 구간의 점수를 계산하기 위해서 작은 구간의 최대 점수부터 차례대로 큰 구간의 점수를 찾아가는 형태의 순회를 해야 한다. 또한 주어진 조건에 따라 기본 풍선 점수 표 양 끝에 1점의 임의 점수를 추가해주면 문제를 코드를 작성하기에 편의성이 생긴다. 이러한 점들을 고려하며 통과한 최종 코드는 아래와 같다.

public class Solution {  
    public int maxCoins(int[] nums) {  
        int[] arr = new int[nums.length + 2];  
        for(int i = 0; i < nums.length; i++){  
            arr[i + 1] = nums[i];  
        }  
        arr[0] = 1;  
        arr[arr.length - 1] = 1;  
        int n = arr.length;  
  
        int[][] dp = new int[n][n];  
  
        for(int k = 0; k < n - 2; k++){  
            for(int l = 1; l + k <= n - 2; l++){  
                int r = l + k ;  
                for(int j = l; j <= r; j++){  
                    int front = dp[l][j - 1];  
                    int shoot =  arr[l - 1] * arr[j] * arr[r + 1];  
                    int back = dp[j + 1][r];  
  
                    dp[l][r] = Math.max(dp[l][r], front + shoot + back);  
                }  
            }  
        }  
  
        return dp[1][n - 2];  
    }  
  
}

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

배열 내에 값이 증가하는 최대 길이를 찾는 문제이다. 현재 값 보다 이전의 작은 값들일 때의 길이 값을 알면 1을 더하여 현재 최대 가능 길이 값을 구할 수 있다. 이전에 현재 값보다 작은 값이 없다면 1이 된다.

DP 배열을 만들어 배열에 길이 값을 저장하여 문제를 풀어주었다. 아래의 코드와 같이 다이나믹 프로그래밍 방식으로 풀어 통과하였다.

public class Solution {  
    public int lengthOfLIS(int[] nums) {  
        int[] dp = new int[nums.length];  
        dp[0] = 1;  
  
        int answer = 1;  
        for(int i = 1; i < nums.length; i++){  
            int num = nums[i];  
            int search = i;  
            dp[i] = 1;  
            while(search-- > 0){  
                int compare = nums[search];  
                if(compare < num){  
                    dp[i] = Math.max(dp[search] + 1, dp[i]);  
                }  
            }  
  
            answer = Math.max(dp[i], answer);  
        }  
  
        return answer;  
    }  
}

문제 풀이 후 다른 해답 중에 이진 탐색을 쓰는 경우도 있었다. 숫자 배열을 만들고 정렬하며 현재의 num 값을 삽입해주는 형태였다. 삽입 해주어야 하는 인덱스를 이진 탐색을 이용할 경우 DP로 풀때 O2 의 시간복잡도를 갖지만, 이진탐색의 경우 O(n log(n)) 의 시간복잡도로 더욱 빠르게 해결되는 것으로 확인하였다. 아래와 같이 java의 이진 탐색 메서드를 통해 쉽고 더 빠른 구현이 가능하다.

public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

https://leetcode.com/problems/swim-in-rising-water/

각 좌표에 물이 차올라 있어 최소 통과 가능 시간이 정해져 있을 때 최종 좌표까지 도달할 수 있는 최소 시간을 구하는 문제이다. bfs 그래프 문제로 순환하며 풀었으며, 제한 사항을 관리하기 위하여 최소방문 시간 그리드를 이용하였다.

특정 좌표 (r,c) 에 대하여 최소 통과 가능 시간은 해당 그리드의 값이고, 실제로 통과한 시간은 다른 그리드를 거쳐 도착했을 때의 최소 시간이다. 다른 그리드를 거쳐 도착했을 때의 시간이 해당 그리드의 최소 시간 이전일 경우 해당 그리드에서 해당 시간까지 대기해야 하기 때문에 Math.max를 이용하여 시간을 체크 해주었다. 또한 다른 경로로 도착했을 때 그보다 빠르게 도착하는 방법이 있을 경우 해당 순환은 불필요하기에 크기 비교를 통하여 경로 필터를 해주었다. 아래는 최종 통과코드이다.

import java.util.*;  
  
public class Solution {  
  
    public int swimInWater(int[][] grid) {  
  
        int m = grid.length;  
        int n = grid[0].length;  
        int[][] minTimes = new int[m][n];  
        for(int i = 0; i < m; i++){  
            Arrays.fill(minTimes[i], Integer.MAX_VALUE);  
        }  
        minTimes[0][0] = grid[0][0];  
        bfs(grid, minTimes);  
  
        return minTimes[m - 1][n - 1];  
    }  
  
    private void bfs(int[][] grid, int[][] minTimes){  
  
        int[] dr = {-1,0,1,0};  
        int[] dc = {0,-1,0,1};  
  
        Queue<int[]> q = new ArrayDeque<>();  
        q.add(new int[]{0,0});  
  
        while(!q.isEmpty()){  
            int[] now = q.poll();  
            int r = now[0];  
            int c = now[1];  
  
            for(int i = 0; i < 4; i++){  
                int nextRow = r + dr[i];  
                int nextCol = c + dc[i];  
                int time = minTimes[r][c];  
  
                if(nextRow >= 0 && nextRow < grid.length  
                        && nextCol >= 0 && nextCol < grid[0].length  
                ){  
                    int nextTime = Math.max(time, grid[nextRow][nextCol]);  
                    if(minTimes[nextRow][nextCol] > nextTime){  
                        minTimes[nextRow][nextCol] = nextTime;  
                        q.add(new int[]{nextRow, nextCol});  
                    }  
                }  
            }  
        }  
    }  
}

특정 강의를 듣기 위해서 다른 강의를 들어야 하는 정보가 주어질 때 정상적으로 강의를 들을 수 있는 지에 대한 문제이다. 강의의 관계가 순환 참조 되는 경우 불가능하다고 판단해야 한다.

처음에는 dfs 백트래킹 방식으로 해결하려 하였으나 시간 초과가 되었다. 알고리즘을 바꿔야 하나 고민도 했지만 같은 관계를 여러 번 반복해서 검사를 수행하는 경우가 생긴다는 문제를 알게 되었다. 동일 경로에 대해 어떻게 처리할까 고민하던 중 일반적인 visited를 boolean으로 사용하는 방식 대신 int를 이용하여 미방문,방문,경로완료의 형태로 세가지 상태로 visited 배열을 관리하여 해결해 보았다. 결과적으로 시간 초과의 문제를 해결하고 통과할 수 있었다.

import java.util.*;  
  
public class Solution {  
  
    static int VISITED = 1;  
    static int COMPLETE = 2;  
  
    public boolean canFinish(int numCourses, int[][] prerequisites) {  
        List<Integer>[] preCourse = new ArrayList[numCourses];  
        for(int i = 0; i < numCourses; i++){  
            preCourse[i] = new ArrayList<Integer>();  
        }  
  
        for(int[] info : prerequisites){  
            int course = info[0];  
            int need = info[1];  
  
            preCourse[course].add(need);  
        }  
  
        int[] visited = new int[numCourses];  
        for(int i = 0; i < numCourses; i++){  
            if(preCourse[i].isEmpty()) continue;  
            if(!isPossible(i, preCourse, visited)){  
                return false;  
            }  
        }  
  
        return true;  
    }  
  
    private boolean isPossible(int course, List<Integer>[] preCourse, int[] visited){  
  
        if(visited[course] == COMPLETE){  
            return true;  
        }  
  
        if(visited[course] == VISITED){  
            return false;  
        }  
  
        visited[course] = VISITED;  
  
        for(int pre: preCourse[course]){  
            if(!isPossible(pre, preCourse, visited)){  
                return false;  
            };  
        }  
  
        visited[course] = COMPLETE;  
        return true;  
    }  
  
}

주어진 문자열 배열의 최대 길이의 동일 prefix 를 찾는 문제이다.
로드맵상 Trie 문제로 열심히 풀었으나... 사실 단순히 String 클래스의 startsWith 메서드를 쓰는게 더 편하다는 사실을 후에 알았다.

그럼에도 일단 문제를 통과했으니 해결한 코드를 소개한다.
Trie 구조에 repeat이란 int 값을 추가해주었다. 저장되는 문자들의 동일한 문자가 반복 저장되는 부분을 추가해준 것이다. 따라서 repeat 값을 보면 해당 문자까지 동일한 prefix를 갖는 문자열의 개수를 알 수 있다. 아래는 완성코드이다.

public class Solution {  
    public String longestCommonPrefix(String[] strs) {  
        Trie root = new Trie();  
        for(String str: strs){  
            Trie head = root;  
            char[] c = str.toCharArray();  
            for(int i = 0; i < c.length; i++){  
                int check = c[i] - 'a';  
                if(head.next[check] == null){  
                    head.next[check] = new Trie();  
                }else{  
                    head.next[check].repeat++;  
                }  
                head = head.next[check];  
            }  
        }  
  
        StringBuilder sb = new StringBuilder();  
        Trie head = root;  
        while(head != null){  
            Trie[] next = head.next;  
            boolean isExist = false;  
            for(int i = 0; i < next.length; i++){  
                if(next[i] != null && next[i].repeat == strs.length){  
                    isExist = true;  
                    sb.append(Character.toString(i + 'a'));  
                    head = next[i];  
                    break;  
                }  
            }  
  
            if(!isExist) break;  
        }  
  
        return sb.toString();  
    }  
  
    private static class Trie{  
        Trie[] next;  
        int repeat;  
  
        Trie(){  
            next = new Trie[26];  
            repeat = 1;  
        }  
    }  
}

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

주어진 보드의 문자를 연결해서 타겟으로 하는 문자열이 존재하는지 체크하는 문제이다.
기본적인 DFS 백트래킹으로 문제를 풀 수 있다. 보드의 상하좌우 탐색, 방문 체크, 조건 체크와 boolean 값 리턴 등에서 오류가 나지 않게 처리해주면 무난히 풀 수 있었다. 최종 코드는 아래와 같다.

public class Solution {  
  
    int[] dr = {1, 0, -1, 0};  
    int[] dc = {0, 1, 0, -1};  
    boolean[][] visited;  
  
    public boolean exist(char[][] board, String word) {  
        int m = board.length;  
        int n = board[0].length;  
        visited = new boolean[m][n];  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                if(board[i][j] == word.charAt(0)){  
                    visited[i][j] = true;  
                    if(dfs(board, i, j, 0, word)){  
                        return true;  
                    };  
                    visited[i][j] = false;  
                }  
            }  
        }  
  
        return false;  
    }  
  
    private boolean dfs(char[][] board, int r, int c, int idx, String word){  
        if(idx == word.length() - 1){  
            return true;  
        }  
  
        if(idx > word.length() - 1){  
            return false;  
        }  
  
        int nextIdx = idx + 1;  
        for(int dir = 0; dir < 4; dir++){  
            int nextRow = r + dr[dir];  
            int nextCol = c + dc[dir];  
            if(nextRow >= 0 && nextRow < board.length  
                    && nextCol >= 0 && nextCol < board[0].length  
                    && !visited[nextRow][nextCol]  
                    && board[nextRow][nextCol] == word.charAt(nextIdx)  
            ){  
                visited[nextRow][nextCol] = true;  
                if(dfs(board, nextRow, nextCol, nextIdx, word)){  
                    return true;  
                };  
                visited[nextRow][nextCol] = false;  
            }  
        }  
  
        return false;  
    }  
}

같은 형태로 문자열 배열을 체크하는 문제가 있었는데 해당 문제는 상당히 어려웠었다. 이 문제를 해결한 이후 Trie 자료구조 알고리즘을 공부했다면 도전할 만 하다.

https://ygs3004.tistory.com/93