Stack 대표 문제 풀기

이번 포스트에서는 Stack과 관련된 문제를 풀어보겠습니다.

 

 

풀이는 코드에 직접 적었습니다.

혹시나 궁금하신 부분이 있으시면 댓글로 문의 부탁드립니다.

 

1. Valid Parentheses

Valid Parentheses - LeetCode

풀이

class Solution {
public:
    bool valid(char & c, stack<char> & st) {
        if (st.empty()) {
            return false;
        }
        
        if (c == ')' && st.top() != '(') {
            return false;
        }
        
        if (c == ']' && st.top() != '[') {
            return false;
        }
        
        if (c == '}' && st.top() != '{') {
            return false;
        }

        return true;
    }
    
    bool isValid(string s) {
        // Stack을 준비합니다.
        stack<char> st;
        
        for (auto &c:s) {
            // 만약 parentheses를 여는 경우에는 stack에 넣습니다.
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } 
            // 만약 닫은 문자라면 바로 앞의 문자가 매칭되는 여는 케이스인지 확인합니다.
            else if (valid(c, st)) {
                st.pop();
            } else {
                return false;
            }
        }
        
        // 문자열을 전부 순회한 상태에서는 Stack이 비어 있어야 Valid합니다.
        return st.empty();
    }
};

 

2. Min Stack

Min Stack - LeetCode

풀이

class MinStack {
public:
    // 현재값과, 현재값이 들어오는 시점에서의 최소를 pair로 저장하는 stack을 생성합니다.
    stack<pair<int,int>> s;
    
    MinStack() {}
    
    void push(int val) {
        
        // 만약 stack이 비어있으면, 바로 추가하면 됩니다.
        if (s.empty()) {
            // 최초로 들어온 값이기 때문에 최솟값 = val이 됩니다.
            s.push(make_pair(val, val));
            return;
        }
        
        // stack의 꼭대기에 있는 원소에서 최솟값을 구하고, 현재값과 비교합니다.
        // 즉, min_val은 val이 들어온 시점에서의 최솟값입니다.
        int min_val = min(val, s.top().second);
        
        // pair를 추가합니다.
        s.push(make_pair(val, min_val));
    }
    
    void pop() {
        // 가장 위의 원소를 제거합니다.
        s.pop();
    }
    
    int top() {
        // 가장 위의 원소에서 첫번째 값(원래 들어온 val 값)을 반환합니다.
        return s.top().first;
    }
    
    int getMin() {
        // 가장 위의 원소에서 두번쨰 값(val을 들어올 당시의 최솟값)을 반환합니다.
        return s.top().second;
    }
};

3. Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation - LeetCode

풀이

class Solution {
public:
    long long pop_number(stack<long long> & st) {
        long long ret = st.top();
        st.pop();
        
        return ret;
    }
    
    int evalRPN(vector<string>& tokens) {
        
        // 현재까지 나온 숫자를 저장하는 stack을 생성합니다.
        // 기호가 나오기 전까지는 숫자를 stack에 넣고, 
        // 기호가 나오면 앞에 2 개를 꺼내서 연산을 한 후 결과를 다시 스택에 넣습니다.
        // long long을 사용하는 이유는 곱셈 시에 int 범위를 넘어갈 수 있기 때문입니다.
        stack<long long> st;
        
        for (auto &token:tokens) {
            // +, -, *, / 가 나오는 경우 최근 2개의 숫자를 stack에서 꺼냅니다.
            // 주의할 점은 연산 시에 뒤에 꺼낸 원소가 앞에 와야 한다는 것입니다.
            // 즉, num1보다 num2가 연산 기호 앞에 있어야 합니다. 
            // 만약 순서를 변경하면 -, / 연산에서 오류가 발생합니다.
            if (token == "+") {
                long long num1 = pop_number(st);
                long long num2 = pop_number(st);
                st.push(num2 + num1);
            } else if (token == "-") {
                long long num1 = pop_number(st);
                long long num2 = pop_number(st);
                st.push(num2 - num1);
            } else if (token == "*") {
                long long num1 = pop_number(st);
                long long num2 = pop_number(st);
                st.push(num2 * num1);
            } else if (token == "/") {
                long long num1 = pop_number(st);
                long long num2 = pop_number(st);
                st.push(num2 / num1);
            } 
            // 만약 기호가 아니면 Stack이 넣습니다. 이때 stoi 함수(string to int)를 사용하면 문자열을 숫자로 변경해줍니다.
            else {
                st.push(stoi(token));
            }
        }
        
        return st.top();
    }
};

 

 

4. Generate Parentheses

Generate Parentheses - LeetCode

풀이

class Solution {
public:
    void helper(int n, int open_count, int close_count, string curr, vector<string> & ans) {
        
        // 만약 open과 close 개수가 같은데 둘 다 N개라면, Valid한 케이스입니다.
        if (open_count == n && close_count == n) {
            ans.push_back(curr);
            return;
        }
        
        // open_count가 N보다 큰 경우나 close_count가 open_count보다 큰 경우는 발생할 수 없기 때문에
        // 그냥 recursion을 빠져나옵니다.
        if (open_count > n || close_count > open_count){
            return;
        }
        
        
        // 현재에서 하나 더 열었을 때
        helper(n, open_count + 1, close_count, curr + "(", ans);
        
        // 현재에서 하나 닫았을 때
        helper(n, open_count, close_count + 1, curr + ")", ans);
        
    }
    vector<string> generateParenthesis(int n) {
        // 정답 배열을 생성합니다.
        vector<string> ans;
        
        // helper 함수를 초기값과 함께 호출합니다.
        // 처음에는 빈 문자열이고 open_count와 close_count는 0이 됩니다.
        helper(n, 0, 0, "", ans);
        
        return ans;
    }
};

 

5. Daily Temperatures

Daily Temperatures - LeetCode

풀이

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 현재 온도와 인덱스를 pair로 하는 stack을 생성합니다.
        // 만약 큰 수가 나왔을때, 해당 온도가 이전에 stack쌓인 온도보다 크면 정답을 업데이트 합니다.
        // 즉, 자신보다 큰 수를 처음 봤을때만 정답이 업데이트 됩니다.
        stack<pair<int,int>> st;
        const int n = (int)temperatures.size();
        
        // 초기값은 전부 0입니다.
        // 만약 정답이 업데이트되지 않는다면 해당 인덱스 이후에 자신보다 큰 온도값이 없었다는 의미입니다.
        // 다른 말로 하면, ans[i] == 0이면 해당 index는 stack에 있다는 의미입니다. 
        // (stack은 반드시 내림차순, 왜냐하면 자신보다 큰 수를 보면 stack에서 빠져나오기 때문)
        vector<int> ans(n, 0);
        
        for (int i = 0; i < n; ++i) {
            
            // 만약 현재 온도가 더 높으면 stack에서 해당 원소를 제거합니다.
            // 이때 두번째 값이 인덱스이므로 해당 인덱스에 정답을 업데이트 합니다.
            while(!st.empty() && temperatures[i] > st.top().first) {
                int target_index = st.top().second;
                ans[target_index] = i - target_index;
                st.pop();                
            }
            
            // 현재 정보를 stack에 추가합니다.
            // 이 시점에서 stack이 비어있지 않다면, stack에 있는 모든 온도는 현재온도보다 큽니다.
            st.push({temperatures[i], i});
        }
        
        return ans; 
    }
};

 

 

6. Car Fleet

Car Fleet - LeetCode

풀이

class Solution {
public:
    bool meet(pair<int,int> & a, pair<int,int> & b, int target) {
        // 두 Car가 만나는 공식: 
        // a_pos + a_speed * 시간 = b_pos + b_speed * 시간
        // 따라서 시간 = (b_pos - a_pos) / (a_speed - b_speed) 이 됩니다.
        int a_pos = a.first, a_speed = a.second;
        int b_pos = b.first, b_speed = b.second;
        
        double t = (b_pos - a_pos) / (double)(a_speed - b_speed);
        
        // 시간이 0보다 작으면 이미 앞서간 차가 더 빠르다는 의미이므로 절대 만나지 않습니다.
        if (t < 0) {
            return false;
        }
        
        // 만약 t시간 후의 위치가 target보다 작거나 같으면 두 Car는 target 이전에 만난다는 의미입니다.
        return t * a_speed + a_pos <= target;
    }
    
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        
        // <position, speed> pair를 위한 배열을 정의합니다.
        // pair값이 필요한 이유는 양쪽 중 하나를 기준으로 배열을 정렬해야하는데, 매핑되는 값이 달라지면 안되기 때문입니다.
        vector<pair<int,int>> arr;
        const int n = (int)position.size();
        
        // position을 기준으로 정렬할 예정이므로 position[i]를 먼저 넣습니다.
        for (int i = 0; i < n; ++i) {
            arr.push_back({position[i], speed[i]});
        }
        
        
        // 위치가 오름차순이 되도록 정렬합니다.
        sort(arr.begin(), arr.end());
        
        // fleet의 대표값을 저장할 stack을 정의합니다.
        // 만약 stack의 요소와 target 이전에 만난다고 하면 stack에 있는 요소를 제거하고,
        // 현재요소를 대표로 추가합니다.
        stack<pair<int,int>> s;
        for (auto &x:arr) {
            
            // stack에 있는 fleet 대표원소들 중에서 현재 Car와 만나는 fleet을 모두 제거합니다.
            while(!s.empty() && meet(s.top(), x, target)) {
                s.pop();
            }
                  
            // 현재 Car를 대표 fleet으로 지정합니다.
            s.push(x);
        }
        return s.size();
    }
};

 

 

7. Largest Rectangle in Histogram

 

Largest Rectangle in Histogram - LeetCode

풀이

class Solution {
public:
    int largestRectangleArea(vector<int>& arr) {
        const int n = (int)arr.size();
        // 이전 히스토그램의 정보를 저장할 stack을 생성합니다.
        stack<int> s;
        
        // -1을 추가합니다. 이유는 아래에서 설명드리겠습니다.
        s.push(-1);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            
            // stack이 비어있지 않고, 스택이 있는 기둥의 높이가 현재보다 큰 경우에는 해당 기둥을 제거합니다.
            // 왜냐하면 작은 기둥 사이에 낀 큰 기둥은 현재기둥 이후로는 쓸 수 없기 때문입니다.
            while(s.top() != -1 && arr[s.top()] > arr[i]) {
                
                // 여기서 가장 최근값을 꺼냅니다. 즉, 이후에는 두번째 최근값이 존재합니다.
                int idx = s.top();
                s.pop();
                /*
                현재 기둥의 위치 = i, 제거할 기둥의 위치: idx, 제거할 기둥보다 이전에 있었으며 제거할 기둥보다 작은 기둥의 위치 = s.top()
                예를 들어 stack [1,2,5]인 상황에서 i = 3이면, idx = 5, s.top() = 2 가 됩니다.
                여기서 높이가 arr[idx]인 사각형의 왼쪽 기준은 s.top() + 1 위치 기둥, 사각형의 오른쪽 기준 = i-1 위치입니다.
                이유는 자신보다 큰 기둥들은 모두 stack에서 제거해왔기 때문입니다.
                
                위 예시에서 보시면 [1,2,5] 중 2번째 기둥과 5번째 기둥 사이에 5번째 기둥보다 큰 기둥은 있을 수 없습니다.
                따라서 2번째 기둥 다음부터는 길이가 모두 5 이상은 된다는 의미입니다.
                
                앞에서 -1을 넣은 이유도 바로 이 때문입니다. 만약 현재 기둥이 가장 작은 기둥이라면, 그 바로 전 기둥의 위치는 존재하지 않습니다.
                따라서 -1을 추가하여 s.top() + 1 기둥이 0번째 기둥이 되도록 한 것입니다. 왜냐하면 0 ~ idx 에 있는 모든 기둥은 현재 기둥보다 크거나 같이 때문입니다.
                */
                ans = max(ans, arr[idx] * (i - 1 - s.top()));
            }
            s.push(i);
        }
        
        // stack에 남은 기둥들을 처리합니다.
        // 이때는 오른쪽 기둥의 위치는 항상 마지막 기둥이 됩니다.
        while(s.top() != -1) {
            int idx = s.top();
            s.pop();
            ans = max(ans, arr[idx] * (n-1 - s.top()));
        }
        
        return ans;
    }
};

 

먼저 가장 간단하게 풀 수 있는 방법은 최소 높이부터 높이를 올려가면서 가장 긴 subarray를 찾아 곱한 후에 그 중 최댓값을 구하면 됩니다. 하지만 이는 O(N * H) 만큼의 시간이 소요됩니다. 따라서 이 방법보다 나은 방안을 찾아야 합니다.

 

우선 히스토그램의 길이가 길어지는 상황과 짧아지는 상황을 생각해보겠습니다.

1) Heights[i-1] <= Heights[i] 

-> 이 경우에는 Height[i-1] 이 i 번째 수 이후에도 사용될 수 있습니다.

 

2) Heights[i-1] > Heights[i]

-> 이 경우에 Heights[i-1] 은 더이상 이후에는 사용할 수가 없습니다. 왜냐면 중간에 Heights[i] 때문에 Heights[i-1] 만큼의 높이를 채울 수 없기 때문입니다. 즉, 다시 말해서 짧은 길이가 나오는 순간에는 이전에 나왔던 긴 길이의 히스토그램들은 사용을 할 수 없다는 의미입니다.

-> 따라서 이런 경우에 길이가 긴 아이들을 사용하여 너비를 구한 후 리스트에서 제거해도 됩니다.

 

위와 같은 구현을 위해서 Stack을 사용하겠습니다. 이때 초기 값을 -1로 넣어놓고 시작합니다. Heights[i-1] > Heights[i] 인 경우에 오른쪽 기둥은 i-1 번째가 됩니다. 왼쪽 기둥은 스택의 맨 위에서 두번째 값이 됩니다. 왜냐하면 아직 스택에 남아 있다는 이야기는 그동안 해당 값보다 작은 값이 나오지 않았다는 의미이고, 그보다 큰 index에 대해서는 모두 stack의 맨 위쪽 값을 가지고 있다는 의미입니다.

 

예를 들어보겠습니다.

스택의 값이 [1,5,7] 이고, 현재 값이 2라고 해보겠습니다.

 

Heights[Stack.top()] = 7 > 2 이므로 7을 제거할 예정입니다. 이때 stack의 두번째 값은 7보다 작은 가장 가까운 히스토그램입니다. 다시 말해, 5와 7 사이에서는 7보다 작은 수가 나올 수 없습니다. 5 와 7 사이에 8,9,10 등 더 큰 기둥들이 있었다면, 이는 7을 처리하는 과정에서 stack에서 제거되었기 때문에 보이지 않는 것입니다. 만약 6이 중간에 나왔다면, stack은 애초에 [1,5,6,7]이 되었을거고, 5보다 작은 값이 있었다면, 5는 stack에서 이미 제거되었어야 합니다. 따라서 높이가 5인 index에 1을 더한 값이 최소 높이 7을 가지는 왼쪽 기둥이 되는 것입니다. 

 

따라서 너비는 Heights[stack.top()] * (현재 index - 1 - stack의 두번째 인덱스) 가 됩니다.

 

---

지금까지 Stack의 대표 문제들을 풀어보았습니다.

Stack 자료구조는 다른 알고리즘과 곁들어서 많이 출제됩니다. 다른 포스트에서 다양한 알고리즘을 같이 풀어보시면서 실력을 쌓으시기 바랍니다!

Two pointers 대표 문제 풀기

 

배열과 해시 대표 문제 풀기