꿀잠

https://leetcode.com/problems/largest-rectangle-in-histogram/

배열로 높이가 주어지고 각 인덱스의 넓이가 1일 때 만들어지는 사각형 중 가장 큰 크기를 갖고 있는 사각형의 크기를 찾는 문제이다. 사각형을 이루는 모양은 기본적으로 양 쪽의 높이가 현재 이루고 있는 사각형보다 작을 때 해당 시점의 높이에서 최대의 넓이를 가진 사각형이 된다.

이와 같은 성질을 위해서 스택을 이용했다. 값이 순서대로 늘어나는 경우를 저장하고, 값이 감소하는 위치를 확인할 경우 해당 인덱스를 기준으로 이전 인덱스들에서 가능한 사각형의 넓이를 구할 수 있다. 스택에서 값을 하나 씩 빼며 가능한 넓이를 계산하여 최대 값을 확인하고, 해당 높이의 값들을 구했기 때문에 해당 위치의 높이를 낮은 상태라고 가정이 가능하다.

4 - 2 - 1 - 3 와 같은 높이 값이 있다면 아래와 같은 형태로 계산을 해간다.
4
4 - 2
2 - 2
2 - 2 - 1
1 - 1 - 1 - 3
1 - 1 - 1 - 1

1. 4를 스택에 저장한다.
2. 2를 저장해야 하지만 이전 값이 더 크기 때문에 2 보다 큰 스택 안의 값들을 꺼내며 넓이를 구한다.
3. 빼낸 값은 현재의 값으로 다시 저장한다.
4. 1을 저장한다.
5. 크기가 줄어 들었으므로 이전 높이가 2인 경우의 사각형 넓이를 계산한다.
6. 2 높이는 의미가 없어지고 현재 값인 1인 값으로 계산한다.
7. 3 을 저장한다.
8. 배열 전체 순회가 끝난 이후 스택에서 값을 빼며 계산해간다. 3을 계산한 이후 그 이전값으로 변경한 이후 1 높이의 넓이를 구한다.

위와 같은 규칙으로 스택을 이용하여 통과한 최종 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int largestRectangleArea(int[] heights) {  
        int answer = 0;  
        Deque<Integer> stack = new ArrayDeque<>();  
        stack.addLast(heights[0]);  
  
        int width;  
        for(int i = 1; i < heights.length; i++){  
            int h1 = heights[i];  
            width = 1;  
            while(!stack.isEmpty() && stack.peekLast() > h1){  
                int h2 = stack.pollLast();  
                answer = Math.max(h2 * width, answer);  
                width++;  
            }  
  
            while(width-- > 0){  
                stack.addLast(h1);  
            }  
        }  
  
        width = 1;  
        while(!stack.isEmpty()){  
            int h2 = stack.pollLast();  
            answer = Math.max(h2 * width, answer);  
            width++;  
        }  
  
        return answer;  
    }  
}

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

주어진 n의 개수에 따라 열고 닫히는 괄호를 만드는 문제이다. 괄호는 Stack 자료구조 문제 관련해서 자주 등장하는 알고리즘 문제이다. 괄호를 여는 부분이 먼저 나오고 닫히는 부분이 뒤에 나오기 때문에 스택에 저장하고 꺼낼 때 괄호를 완성해 줄 수 있기 때문이다.

하지만 해당 문제는 소괄호 하나만 등장하기 때문에 스택을 특별히 사용할 필요는 없었다. 문자열을 만들면서 열려있는 괄호가 닫히는 괄호가 생성되기 전에 충분히 있는지, 그리고 최종적으로 완성된 문자열의 경우 열고 닫히는 괄호의 숫자가 알맞게 있는지 체크해주면 되었다. 문자열을 생성하는 과정은 백트래킹 형태의 dfs를 이용해 주었고, 효율을 높이기 위해 괄호가 완성되는 형태를 가질 수 없는 경우를 필터링 해주었다. 아래는 통과한 코드이다.

public class Solution {  
  
    static String[] letter = {"(", ")"};  
  
    public List<String> generateParenthesis(int n) {  
        List<String> answer = new ArrayList<>();  
        StringBuilder sb = new StringBuilder();  
        sb.append("(");  
        dfs(n * 2, sb, answer);  
  
        return answer;  
    }  
  
    private void dfs(int n, StringBuilder sb, List<String> answer){  
        boolean isLast = n == sb.length();  
        if(!isPossible(sb.toString(), isLast)){  
            return;  
        }  
  
        if(isLast){  
            answer.add(sb.toString());  
            return;  
        }  
  
        for(int i = 0; i < 2; i++){  
            sb.append(letter[i]);  
            dfs(n, sb, answer);  
            sb.deleteCharAt(sb.length() - 1);  
        }  
    }  
  
    private boolean isPossible(String str, boolean isComplete){  
        int check = 0;  
        for(char c: str.toCharArray()){  
            if(c == '('){  
                check++;  
            }else{  
                if(check == 0){  
                    return false;  
                }  
  
                check--;  
            }  
        }  
  
        return isComplete ? check == 0 : true;  
    }  
  
}

괄호를 체크하기 위해 문자열을 char 배열로 변환해서 해주었는데, 다른 코드들을 참고하니 재귀를 돌면서 left와 right 개수를 단순 int 값으로 처리해서 확인하는 방법이 속도가 좋아서 다음에 괄호 관련된 문제 풀이 시 참고할 방법을 얻을 수 있었다.

https://leetcode.com/problems/daily-temperatures/description/

주어진 온도 배열에서 현재의 온도보다 값이 늘어나기 까지 걸리는 일 수를 구하는 문제이다.
인덱스를 늘리며 스택에 온도가 낮은 경우를 저장해 가며 해결하면 효율적으로 해결할 수 있다.

온도가 올라간 날짜(인덱스)의 경우 스택에서 차례대로 제거되기 때문에 스택에서 제거 가능할 때까지 반복하고, 신규 값을 스택에 넣어주면 된다. int[] 타입을 써도 되지만 가독성과 편의성을 위해 인덱스를 저장하는 별도의 클래스를 만들었다.

완성 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int[] dailyTemperatures(int[] temperatures) {  
  
        int[] answer = new int[temperatures.length];  
        Deque<IdxTemp> stack = new ArrayDeque<>();  
  
        for(int i = 0; i < temperatures.length; i++){  
            int curTemp = temperatures[i];  
  
            // 현재보다 낮은 온도의 이전의 값들을 제거하며 답에 저장  
            while(!stack.isEmpty() && stack.peekLast().temp < curTemp){  
                IdxTemp lowTemp = stack.pollLast();  
                answer[lowTemp.idx] = i - lowTemp.idx;  
            }  
  
            stack.addLast(new IdxTemp(i, curTemp));  
        }  
        return answer;  
    }  
  
    private static class IdxTemp{  
        int idx;  
        int temp;  
  
        IdxTemp(int idx, int temp){  
            this.idx = idx;  
            this.temp = temp;  
        }  
    }  
}

https://leetcode.com/problems/min-stack/description/

최소 값이 min 값을 원할 때 얻을 수 있는 Stack을 구현하는 문제이다. 클래스 안에 내부 배열을 선언하여 해결하였다. 문제를 풀고 찾아보니 Stack 클래스를 직접 이용해도 되는 문제였다. Java에서 제공하는 Stack과 PriorityQueue를 이용하는 방식이 더 쉽게 해결할 수 있을 것으로 예상한다.

우선 본인이 해결한 방식은 배열을 이용했으며, 문제 제약 조건에서 제공한 최대 명령 횟수를 이용하여 배열의 크기를 초기화 해주었다. 배열 크기가 그보다 작다면 push를 해당 횟수만큼 실행할 경우 배열을 넘어서게 될 것이기 때문이다.

0번 index부터 차례대로 넣어주었으며, 현재의 크기 curSize를 이용하여 스택의 최상단 위치를 체크하도록 하였다. 문제에서 요구하는 스택은 최소 값을 확인할 수 있어야 하며 O(n)의 시간 복잡도가 필요하다.

따라서 최소 값을 저장하는 배열도 하나 생성해주었다. push 또는 pop을 할 때 값을 찾고 인덱스를 순차적으로 밀어주거나, 땡겨 주어서 최소 값을 순서대로 정렬해서 저장하였다. 이 때 값을 찾는 index까지의 검색과 해당 index부터 마지막까지의 검색은 for 문을 한 번 순회하기 때문에 O(n)의 시간복잡도 제한 사항을 해결하였다. 순서대로 저장하였기 때문에 min[0]의 값은 현재 스택에 있는 최소 값을 확인할 수 있도록 하였다.

import java.util.*;  
  
class MinStack {  
  
    int[] arr;  
    int[] min;  
    int curSize;  
  
    public MinStack() {  
        arr = new int[3 * (int)Math.pow(10, 4)];  
        min = new int[3 * (int)Math.pow(10, 4)];  
        Arrays.fill(min, Integer.MAX_VALUE);  
        curSize = 0;  
    }  
  
    public void push(int value) {  
        arr[curSize] = value;  
        int minIdx = curSize;  
        for(int i = 0; i < curSize; i++){  
            if(value < min[i]){  
                minIdx = i;  
                break;  
            }  
        }  
  
        for(int i = curSize; i >= minIdx + 1; i--){  
            min[i] = min[i - 1];  
        }  
  
        min[minIdx] = value;  
  
        curSize++;  
    }  
  
    public void pop() {  
        curSize--;  
  
        int value = arr[curSize];  
        int minIdx = curSize;  
        for(int i = 0; i <= curSize; i++){  
            if(value == min[i]){  
                minIdx = i;  
                break;  
            }  
        }  
  
        for(int i = minIdx; i < curSize; i++){  
            min[i] = min[i + 1];  
        }  
  
    }  
  
    public int top() {  
        return arr[curSize - 1];  
    }  
  
    public int getMin() {  
        return min[0];  
    }  
}  
  
/**  
 * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(value); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

https://leetcode.com/problems/valid-parentheses/description/

주어진 문자열의 괄호들이 제대로 닫혀있는지 물어보는 문제이다.
정상적으로 닫혀 있다면 순서대로 닫혀야 하므로 스택을 이용한 문제이다.
스택을 공부할 때 가장 기본적으로 나오는 문제이다. 사실 이와 같은 형태의 문제를 보았을 때 처음 보는 경우에는 왜 스택이 필요한지 이해가 되지 않을 수도 있다.

스택의 개념을 머리에 넣고 주어진 문자열을 차례대로 넣었다가 빼는 것을 확인해 보면 마지막에 넣은 것을 먼저 빼는 스택의 성질이 괄호를 정확히 순서대로 닫아준다는 것을 확인할 수 있다.
아래는 문제를 해결한 코드이다.

import java.util.*;

class Solution {  
    public boolean isValid(String s) {  
	  // Java의 경우 tack, LinkedList 후에 추가된 클라스인 ArrayDeque의 성능이 좋은 것으로 알려져 있다.
        Deque<Character> stack = new ArrayDeque<>();  
        
        for(int i = 0; i < s.length(); i++){  
            char c = s.charAt(i);  
            while(true){  
	         // 1. 스택이 비어있거나, 짝이 맞지 않는다면 문자열을 스택에 넣고 다음으로 넘어간다.
                // 2. 1조건이 맞지 않는다면 스택이 비어있지 않고, isPair(짝) 인 것이기에 
                //    짝에 맞는 스택의 값을 빼내준다. 이후 순차적으로 다시 비교하기 위해 c에 값을 할당 하면 
                //    while 문이 반복되면서 처리한다.
                
                if(stack.isEmpty() || !isPair(stack.peekLast(), c)){  
                    stack.offerLast(c);  
                    break;  
                }else {  
                    stack.pollLast();  
                    if(stack.isEmpty()){  
                        break;  
                    }else{  
                        c = stack.pollLast();  
                    }  
                }  
            }  
        }  
  
	  // 스택이 비어있다면 모든 괄호의 값들이 짝이 맞아 제거 된 것이므로 valid 하다
        return stack.isEmpty();  
    }  
  
    public boolean isPair(char a, char b){  
        return (a =='(' && b ==')')  
                || (a =='{' && b =='}')  
                || (a =='[' && b ==']');  
    }  
}

짝이 맞는 괄호일 때 while 문을 이용하여 연속적으로 확인하여 중첩된 괄호를 확인할 수 있다.
isPair의 경우 신규 값인 b의 값이, 스택에 있던 a의 값을 닫는 형태인지 체크하고 있다.