LeetCode Daily 문제풀기

1833. Maximum Ice Cream Bars

주어진 배열 이 있고 거기서 최대 아이스크림을 살만큼 사면되는 문제이다. 비교적 어제 보다 쉬운 문제이다. 왜냐하면 노트에 표기된 순서에 상관없는 구매가 가능하다는 부분이 이문제를 직관적으로 만든다.

만약 저 노트 부분이 없다면 sliding window 를 이용해 범위를 넓혀나가면서 계산해야지 싶다.

최대범위 10k 이기 떄문에 부담 없이 for loop 돌려도 된다.

정렬을 우선 해주고 o(nlogn), while을 이용해서 작은 가격의 아이스크림부터 우선적으로 챙긴다.

    class Solution {
        public int maxIceCream(int[] costs, int coins) {
            int answer = 0;
            Arrays.sort(costs);

            if(costs[0] > coins) return answer;

            int idx = 0;
            while(coins > 0 && idx < costs.length){
                if(costs[idx] <= coins){
                    answer++;
                    coins -= costs[idx++];
                }else{
                    break;
                }
            }
            return answer;
        }
    }

 

별다를 게 없는 코드이다. 다만 index 의 변수 라던지 answer의 변수를 줄일 수 있을 거 같아 여러 번 고민했다.

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int len = costs.length;

        for(int i=0;i<len;i++){
            if(costs[i] > coins) return i;
            coins -= costs[i];
        }

        return len;
    }
}

이렇게 압축을 시켜줄수 있다. for 문안에서 리턴되는 경우라면? 배열 끝까지 못 사는 경우 

마지막에 리턴이 된다면 ? 플렉스

이거는 미디엄 레벨 이 아니라 이지 레벨로 측정되어야 하지 않는가 싶다.

 

108. Convert Sorted Array to Binary Search Tree

정렬된 배열 을 BST로 바꾸는 로직을 작성하는 문제이다. 높이가 균등한 BST 이기 때문에 한쪽으로 편향된 경우를 제외하자.

 

여기서 BST 가 생소할 수 있다. BST 란 노드 하나 기준으로 외쪽은 노드 본인보다 작고 오른쪽은 본인보다 큰 경우 이다.

즉 다시 말해 위의 답이 2가지 가 될 수 있는 이유이다. 또한 높이가 균등한 BST라고 되어 있기 때문에 왼쪽 높이가 3이라면 오른쪽 높이는 최대 4 최소 2 즉 1의 차이를 가진 트리 그래프를 그려야 한다.

** 여기서 중요한 것은 BST를 구성할 때 노드 좌 우는 본인보다 작고 커야 한다 즉 중간 값이라는 이야기다

 

바로 구현 가보자

 

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int[] arr,int left,int right){
        if(left >right) return null;
        int mid = (left+right)/2;
        TreeNode node = new TreeNode(arr[mid]);
        node.left = helper(arr,left,mid-1);
        node.right = helper(arr,mid+1,right);
        return node;
    }
}

재귀를 이용해서 좌우로 넣어주었다. mid 값 기준으로 좌우로 넣어주되 +1을 해야 하는 이유는 현재 mid 값은 검증된 값 이기 때문이다. 

추가적으로 검증을 할 이유가 없다 저렇게 안 한다면 아마 StackOverFlow를 마주하지 않을까 싶다.

 

110. Balanced Binary Tree

주어진 TreeNode 가 균등한 BST 인지 아닌지 판별하는 문제이다. 아까 말했다시피 높이를 판별해서 true false의 값을 반환해주어야 하는데...  푸는데 시간 좀 들였다.

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        
        int left = helper(root.left,0);
        int right = helper(root.right,0);

        return Math.abs(right-left) > 1 ? false : true;
    }
    public int helper(TreeNode node,int depth){
        if(node == null) return depth;
        int left = helper(node.left,depth+1);
        int right = helper(node.right,depth+1);
        return Math.max(left,right);
    }
}

단순 트리의 깊이를 이용해 좌우측 깊이 판정을 통해 비교하는 값을 했더니만 233번인가 203번 케이스에서 걸린다.

좌우측편향 트리인 경우 true의 값을 리턴하는 문제였다.  / \ 이런 식으로 된 트리구조라면 나의 답은 true로 나오기 때문이다 왜? 좌우측 그냥 가장 깊은 트리의 높이를 반환하니깐

 

재귀 중간중간 높이 체크할 변수가 필요하다. 방법을 찾지 못해 디스커스에 가서 몇몇 해설을 읽었다.

class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) != -1 ;
    }
    public int helper(TreeNode node){
        if(node == null) return 0;

        int left = helper(node.left);
        int right = helper(node.right);

        if(left == -1 || right == -1) return -1;
        if(Math.abs(right-left) > 1) return -1;

        return 1 + Math.max(left,right);
    }
}

이렇게 되면 편향 트리인 경우 2번째 높이에서 1 보다 큰 차이가 있기에 두 번째 If에서 -1 로직을 타면서 false를 리턴한다.

 

오히려 Medium 난이도 인 데일리 문제보다 이 BST 문제가 더 어려웠다.
Easy 난이도인데도 이런 트리문제가 나오면 너무 약하다. 만약 라이브 코딩 을 한다면 이런 트리문제는 흐.... 트리문제 위주로 더 풀어봐야겠다.