밀렸던 릿코드 풀기 (232, 150, 739, 2966, 1291)

릿코드 문제가 영어라 접근하기 쉽지 않지만 그래도 풀어보면 자료구조에 대해 이해할 수 있어서 좋은점이 많다.

 

첫문제는 비교적 쉬운 문제이다.  

232. Implement Queue using Stacks 

처음에 접근할 때는 HashSet 을 사용해보려고 했는데 순서가 보장이 안되더라.. 왜냐하면 내부적으로 해시테이블을 구현하는데 해시함수에 의해서 순서가 달라진다.  LinkedHashSet을 이용하면 풀 수 있을거 같다.(+ 정렬되어있다면 TreeSet을 이용할 수 있다. 추가, 삭제, 조회 작업시 O(logn) 으로 수행된다. )  근데 접근하기 편한 ArrayList 를 써서 풀었다. 😎

Time Complexity 

push - O(1)
pop - O(n) //비효율적 
peek - O(1)
empty - O(1)

Space Complexity

push 
- 추가되는 건 : O(1)
- 그 외 모든 Space Complexity : O(n)
pop - O(1) 
peek - O(1) 
empty - O(1)

class MyQueue {
 
    private ArrayList<Integer> al = null;
 
    public MyQueue() {
        al = new ArrayList<>();
    }
    
    public void push(int x) {
        al.add(x);
    }
    
    public int pop() {
        if (al.size() != 0) {
            int a = al.get(0);
            al.remove(0);
            return a;
        }
        return -1;
    }
    
    public int peek() {
        return al.get(0);
    }
    
    public boolean empty() {
        if (al.size() == 0) {
            return true;
        }
        return false; 
    }
}
 
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

문제에서 다르게 접근하신 분들이 있어서 가져와봤다. 

문제는 push 에서 O(n) 으로 수행된다. 

내꺼랑 또이또이 한걸지도..? 

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
 
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
 
    public void push(int x) {
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        s1.push(x);
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }
 
    public int pop() {
        return s1.pop();
    }
 
    public int peek() {
        return s1.peek();
    }
 
    public boolean empty() {
        return s1.isEmpty();
    }
}

 

150. Evaluate Reverse Polish Notation 

두번째 문제는 부호연산자가 같이 들어올 때 숫자 연산 처리에 대한 것이다. 

반복문 한번에 처리 가능했다. 

Time, Space Complexity - O(n) 

이건 다른 풀이도 봤는데 전형적인 문제풀이라서 생략한다 ! 

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<tokens.length; i++) {
            String token = tokens[i];
            if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                int top = stack.pop();
                int second = stack.pop();
                switch (token) {
                    case "+" :
                        stack.push(top+second);
                        break;
                    case "-" :
                        stack.push(second-top);
                        break;
                    case "*" :
                        stack.push(top*second);
                        break;
                    case "/" :
                        stack.push(second/top);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        } //end of for loop
        return stack.pop();
    }
}

 

마지막 문제는 현재 인덱스를 기억하고 있어야 하는 문제이다. 이전이랑 비교해서 값이 큰지 비교하는 문제이다. 단순히 for loop을 돈다고 해결되는 문제는 아니다. 비교대상은 커져도 된다. 약간 투포인트 같은 느낌..? 

739. Daily Temperatures

Time Complexity : O(n)
Space Complexity : O(n)

 

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[temperatures.length];
        for(int i=0; i<temperatures.length; i++) {
            while(stack.size() != 0 && 
            temperatures[i] > temperatures[stack.peek()]
            ) {
                int a = stack.pop();
                answer[a] = i - a; 
            }
            stack.push(i);
        }
        return answer;
    }
}

 

2966. Divide Array Into Arrays With Max Difference

처음에 접근할 때는 이차원 배열 안에 배열 값 자체를 만들어서 k만큼 차이가 있는지 비교했는데 한번 돌 때 비교하면 쉽게 풀어지더라.

Time Complexity - O(nlogn) 

Arrays.sort 가 퀵소트 알고리즘이랑 유사하다. 

Space Complexity - O(n/3) - O(n)

2차원 배열을 할당하는데 n/3 만큼 할당한다. 

class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums);
        int a = nums.length/3;
        int[][] b = new int[a][3];
        int num = 0;
        for(int i=1; i<=nums.length; i++) {
            b[num][i%3] = nums[i-1];
            if(i%3 == 0) {
                num ++;
            }
        }
        for(int i=0; i<a; i++) {
            for(int j=1; j<3; j++) {
                if(Math.abs(b[i][j]-b[i][j-1]) > k) {
                    return new int[0][];
                }
            }
        }
        return b;   
    }
}

 

to - be

import java.util.Arrays;
 
class Solution {
    public int[][] divideArray(int[] nums, int k) {
        Arrays.sort(nums); 
        if (nums.length % 3 != 0) return new int[0][]; 
        
        int a = nums.length / 3;
        int[][] b = new int[a][3];
        int index = 0; // 부분 배열의 인덱스
        
        for (int i = 0; i < nums.length; i += 3) {
            if (i + 2 < nums.length && nums[i + 2] - nums[i] <= k) {
                b[index][0] = nums[i];
                b[index][1] = nums[i + 1];
                b[index][2] = nums[i + 2];
                index++;
            } else {
                return new int[0][];
            }
        }
        return b; 
    }
}

 

 

1291. Sequential Digits 

이 문제는 low, high 범위 안에 있는 문제를 필터링 하는 것이다. 순차적 숫자는 각 자리의 숫자가 이전 자리의 숫자보다 하나씩 더 큰 특성이 있다. 

9-i 는 순차적 숫자를 구성할 때 각 자리는 이전 자리보다 1만큼 크기 때문에 숫자의 시작점과 길이를 기반으로 가능한 모든 숫자를 순차적으로 생성해야 한다. 

Time Complexity - O(1)

nlow부터 nhigh까지 반복되기 때문에 nhigh-nlow+1 만큼 반복한다. 

내부루프도 최대 9회이다.

Space Complexity - O(n) 

ArrayList에 low 부터 high사이에 존재하는 순차적 숫자값을 저장한다. 

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> answer = new ArrayList<>();
        String k = "123456789";
        int nlow = String.valueOf(low).length();
        int nhigh = String.valueOf(high).length();
        for (int i=nlow; i<=nhigh; i++) {
            for(int j=0; j<=9-i; j++) {
                int num = Integer.parseInt(k.substring(j, j+i));
                if (num >= low && num <= high) {
                    answer.add(num);
                }
            }
        }
        return answer; 
    }
}

 

 

다음에 보고 조금 더 생각해볼 수 있는 부분이 있다면 업데이트 해야겠다.. (미리미리 풀기)