꿀잠

https://leetcode.com/problems/container-with-most-water/description/

배열의 인덱스를 x좌표 값을 y좌표로 물이 들어있는 컨테이너를 만들 때 가장 많은 물 양을 담는 방법을 묻는 문제이다.

두 지점을 선택했을 때 가장 최선의 선택이 되는 경우를 찾는 방법이다.
두 인덱스의 차이는 컨테이너의 너비이며 높이는 두 값 중 더 낮은 값이 된다.

문제를 해결하기 위해 왼쪽 인덱스는 차례대로 증가 시켜 주었으며, 높이의 경우 우측 가장 끝부터 좌측 값보다 높은 경우를 찾아주었다. 좌측 값보다 높다면 사각형의 넓이는 좌측 좌표를 기준으로 최대의 높이인 좌측 높이 값이 될 것이며 우측 끝부터 감소 시키며 순환하기 때문에 너비 또한 좌측 값 기준 최대의 값이기 때문이다. 좌측 값을 끝까지 증가 시키며 순회하면 최선의 값이 나오게 된다.

public class Solution {  
    public int maxArea(int[] height) {  
        int answer = 0;  
        for(int i = 0; i < height.length - 1; i++){  
            for(int j = height.length - 1; j >= i + 1 ; j--){  
                int width = j - i;  
                if(height[i] < height[j]){  
                    answer = Math.max(answer, width * height[i]);  
                    break;  
                }else{  
                    answer = Math.max(answer, width * height[j]);  
                }  
            }  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/contains-duplicate/description/

주어진 배열에 중복된 값이 있는지 체크하는 문제이다.
중복과 관련해서 가장 쉽게 사용할 수 있는 자료구조는 Set 이다.
Set은 중복된 값을 넣을 경우 제거되고 하나의 값으로 저장되기 때문이다.
배열의 값을 순차적으로 넣으며 Set의 크기가 변하는지 확인하여 해결해주었다.

import java.util.*;  
  
public class Solution {  
    public boolean containsDuplicate(int[] nums) {  
        Set<Integer> set = new HashSet<>();  
        int size = 0;  
        for(int i = 0; i < nums.length; i++){  
            size++;  
            set.add(nums[i]);  
            if(size != set.size()) return true;  
        }  
  
        return false;  
    }  
}

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/house-robber/description/

주어진 배열의 값이 집의 돈이라고 할 때, 연속된 집을 훔칠 수 없다면 최선으로 훔쳤을 때의 최대 돈의 값을 계산하는 문제이다. DP 문제로 해결할 수 있으며 점화식을 세워야 한다.

연속되지 않는 것이 중요하기 때문에 특정 위치 n 에서 최대로 훔칠 수 있는 돈은

1. n - 1일까지 최대로 훔치고 n일차에 훔치지 않은 경우
2. n - 2 일차에 훔치고 n - 1 일차에 훔치지 않은 후에 n 일차에 훔치는 경우이다

n - 2 일차를 기준으로 해야 하기에 1일차, 2일차의 경우 조건이 바뀐다.

1. 1일차의 경우 바로 그날을 훔치는 경우
2. 2일차의 경우 1일차에 훔치거나 2일차에 훔치거나이다

문제 조건에서 n = 1부터 가능하므로 이를 if문으로 예외 처리해주고 점화식을 세웠다. 최종적으로 배열의 마지막 값(마지막 날)을 리턴해주면 된다.

public class Solution {  
    public int rob(int[] nums) {  
  
        int[] dp = new int[nums.length];  
        dp[0] = nums[0];  
        if(nums.length == 1) return dp[0];  
  
        dp[1] = Math.max(nums[1], dp[0]);  
        if(nums.length == 2) return dp[1];  
  
        for(int i = 2; i < nums.length; i++){  
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);  
        }  
  
        return dp[nums.length - 1];  
    }  
}