열심히 생각하는 공간

프로그래머스 문제

스택 카테코리에 있지만, ArrayList로 풀었다.

🐾풀이 방식

Math.ceil((double)(100-progress[i])/(double)speed[i]) 을 이용하여 나머지 값을 올림하여 list 에 추가해주었다.

나는 return 값을 염두해 두고 풀어서 좀 지저분하게 푼 것 같다.

다른 사람들의 경우

int progressed=-1;
progresses[i] + (progressed*speeds[i]) < 100

를 사용한 듯하다. 좋은 식이다.

코드

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        List<Integer> list = new ArrayList<>();
        double finDay=Math.ceil((double)(100-progresses[0])/(double)speeds[0]); 
        int progressed=1;
        
        for(int i=1; i<progresses.length; i++) {
            double nowDay = Math.ceil((double)(100-progresses[i])/(double)speeds[i]);
            if(finDay >= nowDay) { // 전일 완료 일자가 당일 완료일자보다 클 때,
                progressed++;
               
            } 
            else if(finDay < nowDay) {  
                list.add(progressed);
                finDay=nowDay; // 몇일 걸리면 끝나는지.
                progressed=1;
            }
            if(i==(progresses.length-1)) list.add(progressed);
        }
        return list.stream()
	           .mapToInt(Integer::intValue)
    	       .toArray();
    }
}

🦉 Double Colon

자료 구조를 ArrayList를 사용한 이유는 Array로 반환하기 쉽겠다 싶어서 였는데, 생각보다 쉽진 않았다.

더블콜론도 처음 써봤다.

클래스를 직접 사용하여 메소드 참조, 호출을 한다.

<class name> :: <mathod name>

import java.util.stream.*; 
  
class GFG { 
    public static void main(String[] args) 
    { 
  
        // Get the stream 
        Stream<String> stream 
            = Stream.of("Geeks", "For", 
                        "Geeks", "A", 
                        "Computer", 
                        "Portal"); 
  
        // Print the stream 
        // using double colon operator 
        stream.forEach(System.out::println); 
    } 
}

참조

Double colon

프로그래머스 문제

LRU 캐시에 대한 문제이다.

🐾 풀이 방식

Queue를 이용하여 풀었다.

현재 Queue 안의 size와 cacheSize를 비교해서 제거하는 것 까지 생각해내는 것이 중요한 듯 싶다.

LRU 알고리즘을 제대로 이해하지 못해서 정말 헤맸었는데 코드 힌트를 보고 다시 공부했다.

코드

import java.util.*;
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        if(cacheSize==0) return cities.length*5;    
        Queue<String> cache = new LinkedList<>();
        
        for(String city : cities) {
            String lowCity = city.toLowerCase();
            if(cache.contains(lowCity)) { // 캐시에 있다면
                cache.remove(lowCity);
                cache.add(lowCity);
                answer+=1;
            } else { // 캐시에 없다면
                if(cache.size()==cacheSize) { // 캐시 사이즈가 찼으면
                    cache.poll(); // 캐시 pop
                }
                // 캐시 공간이 여유로우면
                cache.add(lowCity);
                answer+=5;
            }
            
        }
        return answer;
    }
}

🦉 LRU 알고리즘

간단하게 생각하면 되는데 알고리즘에 대한 궁금증이 생겼다.

cacheSize=5, cities={a, b, c, b, d, e, f}; 일때 LRU 알고리즘을 사용하게 되면

절차가 {a}, {a, b}, {a, b, c}로 쌓다가 a를 pop하고 {b, c, b}가 되는지 아니면 {a, b} 두개를 pop하고 {c, b} 부터 되는지가 궁금했다.

▶ Chat GPT에게 알아본 결과 LRU 지식을 잘못 이해한 것이었다.

아싸에게 너무나 감사한 선생님이다..

내가 헷갈리는 부분을 명확히 짚어줬다.

중복 값이 나오면 해당 index 부터 시작하는 것이 아니라 해당 값을 맨 뒤로 이동시키는 것이 관건이다.

참조

참조한 코드

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

https://leetcode.com/problems/power-of-four/

아직까지 조금 헤매기는 하지만 그래도 실력이 늘고있다고 믿고있다 ㅎㅎ 

하지만 다른사람들의 풀이는 진짜 놀라울 따름이다..

 public static boolean isPowerOfFour(int n) {
        if (n==0) return false;
        double x;
        double doubleN = n;
        x = (Math.log10(doubleN) / Math.log10(4));
        System.out.println("x = "+ x);
        if(isNumeric(x) == true) {
            return true;
        }
        else
            return false;
    }

    public static boolean isNumeric(double x) {
        if(Math.ceil(x) == Math.floor(x)) return true;
        else return false;
    }

double x가 정수인지 아닌지를 판별하는 방법을 생각하던 와중에 다양한 방법을 제시한 사이트를 찾았다. 이 사람들 처럼 창의적인 아이디어가 마구 떠올랐으면 좋겠다.ㅎㅎ

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

https://leetcode.com/problems/flood-fill/

Description보고 이해 안돼서 유투브도 같이 봤다. 

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
	if (image[sr][sc] == newColor) return image;
    fill(image, sr, sc, image[sr][sc], newColor);
    return image;
    
   }
   
 private void fill(int[][] image, int sr, int sc, int color, int newColor) {
 	if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != color) return;
    image[sr][sc] = newColor;
    fill(image, sr+1, sc, color, newColor);
    fill(image, sr-1, sc, color, newColor);
    fill(image, sr, sc+1, color, newColor);
    fill(image, sr, sc-1, color, newColor);
    
    }
  }

참고 코드

참고 영상

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

머리로는 푸는데 코드로 나타내기만 좀 더.. 해야겠다.

Description이 이해가 안되는 중에 정말 설명이 간단하고 잘 된 영상을 발견했다.

public Node connect(Node root) {
        if(root == null) 
            return root;
        
        Node leftNode = root;
        while(leftNode.left != null) {
            Node head = leftNode;
            while(head != null) {
                head.left.next = head.right;
                if(head.next != null) {
                    head.right.next = head.next.left;
                } head = head.next;
            }
           leftNode = leftNode.left;
        }
        return root;
        
    }

참코 코드

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

https://leetcode.com/problems/merge-two-binary-trees/

두 트리의 합을 구해 새 트리를 만드는 문제이다.

그래도 아이디어까진 얼추 맞힌 것 같다.

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        
        TreeNode root3 = new TreeNode(root1.val + root2.val);
      
            root3.left = mergeTrees(root1.left, root2.left);
            root3.right = mergeTrees(root1.right, root2.right);
     
        
        return root3;
    }

참고 코드

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

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

문자열을 끊되, 중복되지 않는 한에서 가장 많이 끊을 수 있는 경우의 수를 구하는 문제이다.

이 문제를 어떻게든 풀고싶어서. . 며칠을 고민하고 풀었는데

간단하지만 직관적인 해설방법을 역시나 찾았다 ㅎㅎ;

  public static List<Integer> partitionLabels(String s) {
        Map<Character, Integer> map = new HashMap();
        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch,i);
        }

        List<Integer> res = new LinkedList();
        int prev = -1;
        int max = 0;

        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            max = Math.max(max, map.get(ch));

            // 끝에 달았을때
            if(max == i) {
                res.add(max - prev) ;
                prev = max;
            }
        }
        return res;
    }

참고 코드

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

https://leetcode.com/problems/generate-parentheses/

n쌍의 괄호가 나올 수 있는 경우의 수를 구하는 문제이다.

이런 문제를 접할때 마다 정말. . 이렇게 간단하게 풀어내는 사람들이 신기할 뿐이다. .

List<String> res = new LinkedList();
    public List<String> generateParenthesis(int n) {
        dfs(new StringBuilder(), 0, n);
        return res;
    }
    private void dfs(StringBuilder sb, int close, int n) {
        if(n==0 && close==0) {
            res.add(sb.toString());
            return;
        }

        //Add open parenthese
        if(n>0) {
            sb.append('(');
            dfs(sb, close+1, n-1);
            sb.setLength(sb.length()-1);
        }

        //Add close parenthese
        if(close>0) {
            sb.append(')');
            dfs(sb, close-1, n);
            sb.setLength(sb.length()-1);
        }
    }

참고 코드

https://leetcode.com/problems/intersection-of-two-linked-lists/

두 ListNode가 교차하는 첫번째 ListNode를 구하는 문제이다.

ListNode를 거꾸로 해서 뒤에서부터 같은지점까지를 반환하게끔 고민했으나 

순번대로 하는게 더 쉬웠음을.. 깨닫는다.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
            
        ListNode pa = headA, pb = headB;
        while(pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }

참고 코드

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

https://leetcode.com/problems/merge-two-sorted-lists/

두 LinkedList의 대소관계를 따져 순차적으로 반환하는 문제이다. while을 쓰기전에 재귀로 풀 수 있는지를 따져보면 좀더 수월할 것 같다.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
      
        
            if(list1.val > list2.val) {
                list2.next = mergeTwoLists(list2.next, list1);
                return list2;
            } else {
                list1.next = mergeTwoLists(list2, list1.next);
                return list1;
            }   
       
    }

참고 코드