[중급 알고리즘] 스택

LIFO의 특성을 활용

 

💚 9935 문자열 폭발

- 문자열 S에서 폭발 문자열 T를 모두 지우는 문제

- 스택에 넣는 것은 (문자열의 인덱스, 폭발 문자열에서 인덱스)

- 현재 문자가 폭발 문자열의 첫 번째 문자와 같으면 스택에 넣는다.

- 다른 경우에 스택에 비어있으면 그냥 넘어간다.

- 다른 경우에 스택이 비어있지 않으면 스택의 가장 위에 있는 것의 폭발 문자열의 인덱스를 가져온다. 이 인덱스를 p라고 한다. 

- 현재 문자가 폭발 문자열의 p + 1와 같으면 스택에 넣는다. (p + 1이 폭발 문자열의 마지막 문자면, 폭발 문자열을 찾은 것이다. 스택에서 폭발 문자열을 지운다.)

- 다르면 스택을 모두 비워버린다.

- 폭발 문자열의 길이가 1이면 스택을 사용할 수 없기 때문에 그냥 for문을 돈다.

 

T가 모두 다른 문자로 구성되어있는 문자열이라는 점에 가능한 풀이다.

 

 strlen :문자열의 길이 반환

 

#include <stack>
#include <cstring>
#include <iostream>

using namespace std;
char a[1000001];
char b[100];
bool erased[1000001];
int main() {
    cin >> a;
    cin >> b;
    int n = strlen(a);
    int m = strlen(b);
    if(m == 1) {
        for(int i = 0;i < n;i++) {
            if(a[i] == b[0]) {
                erased[i] = true;
            }
        }
    }
    else {
        // a의 인덱스, b의 인덱스
        stack<pair<int,int>> s;
        for(int i = 0;i < n;i++) {
            if(a[i] == b[0]) {
                s.push(make_pair(i, 0));
            }
            else {
                if(!s.empty()) {
                    auto p = s.top();
                    // 이전에 삽입된 문자
                    if(a[i] == b[p.second + 1]) {
                        s.push(make_pair(i, p.second + 1));
                        if(p.second + 1 == m - 1) {
                            for(int k = 0;k < m;k++) {
                                auto p = s.top();
                                erased[p.first] = true;
                                s.pop();
                            }
                        }
                    }
                    else {
                        while(!s.empty()) {
                            s.pop();
                        }
                    }
                }
            }
        }
    }
    
    bool printed = false;
    for (int i = 0;i < n;i++) {
        if(erased[i]) continue;
        cout << a[i];
        printed  = true;
    }
    if(!printed) {
        cout << "FRULA\n";
    }
    else {
        cout << '\n';
    }
    
    return 0;
}

💚 6549 히스토그램에서 가장 큰 직사각형 💥

높이는 항상 막대의 높이 중 하나와 일치할 수밖에 없다.

그래서 각각의 막대에 대해 만들 수 있는 가장 큰 직사각형을 찾으려고 한다.

 

모든 막대 x에 대해서, x를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾아야 한다.

x를 높이로 하면서 만들 수 있는 가장 큰 직사각형은 x의 왼쪽에 있는 막대 중에 x보다 작은 첫 번째 막대 left와

x의 오른쪽에 있는 막대 중에서 x보다 높이가 작은 첫 번째 막대 right를 찾아야 한다.

 

왜 스택을 이용하는가?

직사각형의 높이가 비연속적이라는 점을 활용하기 위함이다.

스택에 직사각형의 높이를 추가할 때 스택 안에 있는 직사각형까지는 갈 수 있다라는 점을 전제한다.

중간에 막히는 직사각형은 이미 pop되었다는 점을 활용한다.

 

스택을 사용해 모든 막대를 스택에 한번씩만 삽입하므로 시간복잡도는 $O(N)$이다.

#include <iostream>
#include <stack>

using namespace std;
long long a[100000];
int main() {
    while(true) {
        int n;
        cin >> n;
        if(n == 0) break;
        for(int i = 0;i < n;i++) {
            cin >> a[i];
        }
        
        stack<long long> s;
        long long ans = 0;
        for(int i = 0;i < n;i++) {
            while(!s.empty() && a[s.top()] > a[i]) {
                long long height = a[s.top()];
                s.pop();
                long long width = i;
                // width 계산 방법
                if(!s.empty()) {
                    width = (i - s.top() - 1);
                }
                if(ans < width * height) {
                    ans = width * height;
                }
            }
            s.push(i);
        }
        
        while(!s.empty()) {
            long long height = a[s.top()];
            s.pop();
            long long width = n;
            if(!s.empty()) {
                width = n - s.top() - 1;
            }
            
            if(ans < width * height) {
                ans = width * height;
            }
        }
        
        cout << ans << '\n';
    }
    return 0;
}

💚 3015 오아시스 재결합

위 문제와 유사한 문제이다.

 

예시로 17452386

1은 앞에 뭐 없으니 push

 

7은 앞의 1보다 크므로 1은 7을 볼 수 있다. → 정답에 1을 더해주고

그 뒤의 것들은 1을 앞으로 절대로 볼 수 없다. 즉 스택에서 없어도 좋다. → 1을 스택에서 제거하고 7을 스택에 추가

for(int i = 0;i < n;i++) {
	while(!s.empty()) {
    	if(s.top() < a[i]) {
        	ans += 1;
            s.pop();
        }
        else {
        	break;
        }
    }
    if(!s.empty()) ans += 1;
    s.push(a[i]);
}

 

그런데 여기서 키가 같은 경우도 고려를 해야한다. 스택에 키를 가진 사람의 수도 넣어서 풀어야 한다.

#include <iostream>
#include <stack>

using namespace std;
int a[500000];
int n;
int main() {
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    // 키
    stack<int> s;
    // 동일한 키인 사람 수
    stack<int> c;
    long long ans = 0;
    for(int i = 0;i < n;i++) {
        int h = a[i];
        int cnt = 1;
        while(!s.empty()) {
            // 어차피 a[i] 보다 작은 키는 앞으로 안 보이기 때문
            if(s.top() <= a[i]) {
                ans += (long long) c.top();
                // 연속적으로 키가 동일하면 인원 누적
                if(s.top() == a[i]) {
                    cnt += c.top();
                }
                s.pop();
                c.pop();
            }
            else {
                break;
            }
        }
        // 어차피 a[i]와 동일한 높이는 이미 pop됐기 때문
        if(!s.empty()) {
            ans += 1LL;
        }
        s.push(h);
        c.push(cnt);
    
    }
    cout << ans << '\n';
    return 0;
}