[LeetCode] 문제 복기(322번, 491번, 1372번, 1253번)

322. Coin Change

• 동전의 목록인 coins가 주어진다. coins로 만들어야하는 amount가 주어진다.
• coins로 amount를 만들때 가장 적은수를 사용하는 케이스를 출력해야한다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        // amount가 0이면 만들수 없다
        if(amount == 0) return 0;
        int[] dp = new int[amount+1]; // dp 구현을 위한 공간 할당
        Arrays.fill(dp, Integer.MAX_VALUE); // 각 dp 원소에는 Integer의 최대값으로 초기화
        Arrays.sort(coins); // coins를 오름차순으로 sorting
        List<Integer> coinList = new ArrayList<>(); // Array -> List
        for (int coin : coins) { 
            coinList.add(coin);
        }

        // ap[i] = 금액 i를 만들기 위해 필요한 최소 coin 개수
        for(int money=1; money<=amount; money++){ 
            // money가 coinList에 있으면 최소 개수는 1개가 된다
            if(coinList.contains(money)) {
                dp[money] = 1; // 
                continue;
            }

            // coins를 순회한다
            for (int coin : coins) {
                // dp[money-coin]들을 모두 가져와서 그중 가장 작은 값을 dp[money]로 한다
                if(money > coin){
                    dp[money] = Math.min(dp[money],dp[money-coin]);
                }
            }
            // dp[money]에 +1을 한다, dp[money]가 Integer.MAX_VALUE라면 답을 구할수 없었다는걸 뜻함!
            if(dp[money] !=Integer.MAX_VALUE) dp[money]++;
        }
        // MAX_VALUE가 그대로 유지된 경우라면 답을 구할수 없었다는 뜻이므로 -1 출력
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];

    }
}

---

491. Increasing Subsequences

• nums를 활용해서 증가(또는 같은)하는 부분 수열을 모두 뽑아내는 문제다.( 같아도 됨 )
• 정답의 중복을 제거하기 위해 ArrayList의 contains를 사용했으나 시간초과 발생
• Set을 사용해서 중복된 데이터가 보관되지 않도록 함.
• 깊은 복사,얕은 복사에 대한 개념정리를 할 수 있는 문제.

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

class Solution {

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> result= new ArrayList<>();
        HashSet<ArrayList<Integer>> tempResult= new HashSet<>();

        for(int i=0; i<nums.length; i++){ // nums를 순회한다

            HashSet<ArrayList<Integer>> clone = new HashSet<>(tempResult); // 얕은복사를 통해 값만 복사한다

            // clone에 들어있는 List를 하나씩 꺼낸다
            for (ArrayList<Integer> integers : clone) {
                // List의 마지막 값을 확인해서 현재 넣으려고 하는 nums[i]보다 작거나 같은지 확인한다.
                if(integers.get(integers.size()-1) <= nums[i]){  
                    // tempResult에 넣는다.
                    ArrayList<Integer> clone1 = new ArrayList<>(integers); 
                    clone1.add(nums[i]);
                    tempResult.add(clone1);

                }
            }

            ArrayList<Integer> objects = new ArrayList<>();
            objects.add(nums[i]); // 현재값을 넣는다 ( 추후 작업시 이어붙이기 위함 )
            tempResult.add(objects);


        }


        for (List<Integer> integers : tempResult) {
            if(integers.size()>1){ // 결과중 길이가 1보다 큰 배열만 result에 담는다
                result.add(integers);
            }
        }

        return result;
    }
}

---

1372. Longest ZigZag Path in a Binary Tree

• 주어진 트리를 통해 최대한 지그재그를 많이 그릴수 있는 횟수를 출력하는 문제

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public static int recursive(TreeNode curNode,boolean isNextRight,int zigZagCount){

        if(curNode == null){ // 현재 노드가 null이면 종료
          return zigZagCount-1;
        } 
        else{

            int right = 0;
            int left = 0;
            // move to right
            if(isNextRight){ // 다음번 움직일 곳이 오른쪽인 경우
                right = recursive(curNode.right,false,zigZagCount+1); // zigZagCount +1로 초기화 하고 오른쪽으로 이동
                left = recursive(curNode.left,true,1); // 왼쪽으로 가는 경우는 zigZagCount를 1로 초기화한다
            }


            // move to left
            if(!isNextRight){ // 다음번 움직일 곳이 왼쪽인 경우
                left = recursive(curNode.left,true,zigZagCount+1); // zigZagCount +1로 초기화 하고 왼쪽으로 이동
                right = recursive(curNode.right,false,1); // 오른쪽으로 가는 경우는 zigZagCount를 1로 초기화한다
            }

            // 가장큰값을 구한다
            return Math.max(right,left);
        }

    }

    public int longestZigZag(TreeNode root) {

        int right = recursive(root,true,0); // 시작점은 root, 다음번 움직일 곳은 오른쪽이다.
        int left = recursive(root,false,0); // 시작점은 root, 다음번 움직일 곳은 왼쪽이다.
        return Math.max(right,left);
    }
}

---

1253. Reconstruct a 2-Row Binary Matrix

• 상단 배열에서 쓸수 있는 1의 개수 upper와 하단 배열에서 쓸수 있는 1의 개수 lower가 주어진다.
• 상단,하단 배열을 적절히 활용해서 colsum을 만들 수 있는 케이스 중 하나를 출력하는 문제

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        List<List<Integer>> result= new ArrayList<>();

        // colsum의 합이 upper + lower보다 크면 정답을 구할 수 없다
        // if sum(colsum) > upper + lower is true, exit
        int sum = Arrays.stream(colsum).sum();
        if(sum > upper + lower) return result;

        int originalUpper = upper;
        int originalLower = lower;
        result.add(new ArrayList<>()); // 정답 상단
        result.add(new ArrayList<>()); // 정답 하단

        // upper와 lower중 큰 숫자를 먼저 쓰자.
        for (int col : colsum) { // colsum을 순회한다
            int upperNumber = 0;
            int lowerNumber = 0;
            if(col == 2){ // col이 2면 상단,하단 모두 1이 필요하다
                upper--;
                lower--;
                upperNumber = 1;
                lowerNumber = 1;
            } else if(col==1){ // col이 1이면 상단에 쓸지 하단에 쓸지 찾아야한다
                if(upper > lower){ // upper가 더크면 upper를 사용한다
                    upper--;
                    upperNumber = 1;
                } else { // 그게 아니면 lower를 사용한다
                    lower--;
                    lowerNumber = 1; 
                }
            }

            result.get(0).add(upperNumber); // 상단 데이터 입력
            result.get(1).add(lowerNumber); // 하단 데이터 입력


        }

        // 상단과 하단의 데이터중 하나라도 음수면 정답을 구할 수 없는 경우다
        if(upper <0 || lower <0) { 
            result.clear();
            return result;
        }

        // 상단과 하단에서 사용한 1의 개수가 문제에서 제시된것과 다르면 정답을 구할 수 없는 경우다
        int upperSum = result.get(0).stream().mapToInt(s -> s).sum();
        int lowerSum = result.get(1).stream().mapToInt(s -> s).sum();
        if(originalUpper != upperSum || originalLower != lowerSum){
            result.clear();
            return result;
        }

        // 정답 출력
        return result;
    }
}