꿀잠

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

문자열을 검색하는 커스텀 클래스를 만드는 문제이다.
Trie 자료구조를 이용해서 문제를 해결할 수 있다. Trie 자료구조란 문자열을 저장할 때 각 노드에 대한 자식 노드를 포인트 배열로 저장하는 형식이다.

해당 문제에선 "." 일 경우 검색 시 모든 문자가 가능하다는 조건이 있고 해당 부분이 문제의 핵심 부분이다. 조건문을 이용하여 해당 부분을 분기 처리하여 해결하였다. 노드를 List 형식으로 하여 순회하였으며, "." 일 경우 연결되는 모든 노드를 List에 전부 추가하여 주었다.

모든 순회가 끝난 이후 마지막 노드들 중 isLast가 있을 경우 검색이 성공한 것이므로 True를 반환하였다. 만약 최종 순회 후 List가 비어있을 경우 result의 초기 값인 false가 반환되며 이는 주어진 문자열에 알맞게 마지막까지 이어지는 글자가 없는 것을 의미한다.

import java.util.*;  
  
class WordDictionary {  
  
    WordNode root;  
  
    public WordDictionary() {  
        this.root = new WordNode();  
    }  
  
    public void addWord(String word) {  
  
        WordNode before = this.root;  
  
        for(int i = 0; i < word.length(); i++){  
            int cur = word.charAt(i) - 'a';  
  
            if(before.next[cur] == null){  
                before.next[cur] = new WordNode();  
            }  
  
            before = before.next[cur];  
        }  
  
        before.isLast = true;  
    }  
  
    public boolean search(String word) {  
        List<WordNode> beforeList = new ArrayList<>();  
        WordNode start = this.root;  
        beforeList.add(start);  
        boolean result = false;  
        for(int i = 0; i < word.length(); i++){  
            char cur = word.charAt(i);  
            List<WordNode> nextList = new ArrayList<>();  
  
            for(WordNode before : beforeList){  
                if(cur == '.'){  
                    for(int j = 0; j < 26; j++){  
                        WordNode next = before.next[j];  
                        if(next != null){  
                            nextList.add(next);  
                        }  
                    }  
                }else{  
                    WordNode next = before.next[cur - 'a'];  
                    if(next != null){  
                        nextList.add(next);  
                    }  
                }  
  
            }  
            beforeList = nextList;  
        }  
  
        for(WordNode next: beforeList){  
            result = result || next.isLast;  
        }  
  
        return result;  
    }  
  
    private static class WordNode{  
        WordNode[] next;  
        boolean isLast;  
  
        WordNode(){  
            this.next = new WordNode[26];  
            isLast = false;  
        }  
    }  
}  
  
/**  
 * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */

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