리트코드 16일차

452. Minimum Number of Arrows to Burst Balloons

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a,b) -> Integer.compare(a[0], b[0]));
        List<int[]> section = new ArrayList<>();

        int start = points[0][0];
        int end = points[0][1];
        
        for (int i = 1; i < points.length; i++){
            if (points[i][0] <= end) {
                start = Math.max(start, points[i][0]);
                end = Math.min(end, points[i][1]);
            }else{
                section.add(new int[] {start, end});
                start = points[i][0];
                end = points[i][1];
            }
        }


        return section.size()+1;
    }
}

간단하게 풀기는 풀었는데, 시간을 더 줄여보고 싶다.

sort 자체에서 시간을 많이 잡아먹는다고 생각했는데 다른 풀이들을 보니 다들 비슷해서 일단 문제 의도는 맞게 푼 것 같다.

 

20. Valid Parentheses

새로운 단원이다. Stack 이다. 이거 배우면 자바에서도 bfs, dfs 가능할 것이다. 아마도..

 

class Solution {
    public boolean isValid(String s) {
        Stack<Character> parentheses = new Stack<>();
        boolean check = true;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == ')'){
                if (parentheses.size() == 0 || parentheses.pop() != '('){
                    check = false;
                    break;
                }
            }else if (s.charAt(i) == '}') {
                if (parentheses.size() == 0 ||parentheses.pop() != '{'){
                    check = false;
                    break;
                }
            } else if (s.charAt(i) == ']' ){
                if (parentheses.size() == 0 ||parentheses.pop() != '['){
                    check = false;
                    break;
                }
            }else{
                parentheses.push(s.charAt(i));
            }
        }
        if (parentheses.size() > 0){
            check = false;
        }
        return check;
    }
}

1학년때풀었던 문제다. 그때도 재밌었지만 지금도 재밌다.

코드 보니까 java 에 map 이 있던데 그거 사용하면 중복 코드를 줄일 수 있던 것 같다.

 

71. Simplify Path

class Solution {
    public String simplifyPath(String path) {
        String[] directories = path.split("/");
        Stack<String> pathStack = new Stack<>();
        String simplify = "";

        for (int i = 0; i < directories.length; i++){
            if (directories[i].equals("..")){
                if (pathStack.size() > 0) {
                    pathStack.pop();
                }
            }else{
                if ((directories[i].length() > 0) && (!directories[i].equals("."))){
                    pathStack.push(directories[i]);
                }
            }
        }

        int size = pathStack.size();
        if (size == 0){
            simplify = "/";
        }
        for (int i = 0; i < size; i++){
            simplify = "/" + pathStack.pop() + simplify;
        }
        return simplify;
    }
}

풀긴풀었는데, 코드가 복잡해보인다.

class Solution {
    public String simplifyPath(String path) {
        String[] directories = path.split("/");
        Stack<String> pathStack = new Stack<>();
        String simplify = "";

        for (int i = 0; i < directories.length; i++){
            if (directories[i].equals("..")){
                if (!pathStack.isEmpty()) {
                    pathStack.pop();
                }
            }else{
                if ((directories[i].length() > 0) && (!directories[i].equals("."))){
                    pathStack.push(directories[i]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while(!pathStack.isEmpty()) {
            sb.insert(0, "/" + pathStack.pop());
        }

        return sb.length() == 0 ? "/" : sb.toString();
    }
}

isEmpty 라는 좋은 함수가 있었다. 그리고 StringBuilder 도. 좋은 접근 같다.

 

155. Min Stack

익숙한 향이 느껴진다. 간단하게 구현하는 스택이다. 나머지는 쉬운데 getMin 구하는게 가장 까다롭다. 나머지는 stack 으로 해결하면 되는데 Min을 O(1) 에 구해야한다. 그런데 아무리 생각해도 방법을 모르겠다.

신기한 답을 보았다.

class MinStack {
    Stack<Integer> st;
    int min = Integer.MAX_VALUE;

    public MinStack() {
        st = new Stack<>();
    }
    
    public void push(int val) {
        if (val<=min){
            st.push(min);
            min = val;
        }
        st.push(val);
    }
    
    public void pop() {
        if (st.pop() == min) min=st.pop();
    }
    
    public int top() {
        return st.peek();
    }
    
    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

무슨코드인지 이해 못하고 있었는데 꽤나 재밌는 코드였다. 쉽게 설명하자면 stack 자체에 min 값도 같이 넣는 거였다.

아래와 같이 동작한다.

 

PUSH(2)    → stack: [2],          min: 2
PUSH(0)    → stack: [2, 2, 0],     min: 0
PUSH(3)    → stack: [2, 2, 0, 3],  min: 0
PUSH(0)    → stack: [2, 2, 0, 3, 0, 0], min: 0

GETMIN()   → 0

POP()      → stack: [2, 2, 0, 3, 0], min: 0
GETMIN()   → 0

POP()      → stack: [2, 2, 0, 3], min: 0
GETMIN()   → 0

POP()      → stack: [2, 2, 0], min: 2
GETMIN()   → 2

min 값이 아니면 하나씩 저장하는데 min값을 새로 업데이트 하는 경우에는 스택에 min값을 같이 쌓아준다. 그러면 나중에 min 값을 pop하는 경우에도 다시 min 값을 복원할 수 있었다. 재밌는 접근이었다.

 

완료!