알고리즘 문제풀이 - 스택, Stack 총정리

 

사실 스택을 이용하는 문제는 수없이 많다. 글 하나로 정리를 할 수 없다는 것은 안다.

하지만 스택이 가리키는 것은 단 하나 밖에 없고 그 개념을 조금이라도 감을 잡고자 글을 쓴다.

 

---

실전 개념

 

1. 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있다.

 

2. Push, Pop은 O(1)의 시간복잡도를 가진다.

 

3. Stack에 최근에 들어간 것만 뺄 수 있다.

=> 가장 마지막에 들어간 것만 뺄 수 있다.

확장 3. 연속된 원소를 집어넣으면 뺄 때는 역순으로 나온다.

 

---

문제를 풀면서 저 1,2,3번의 개념이 어디에 들어가나 보자

 

1. 단어 뒤집기

사실 어려운 문제다.

https://www.acmicpc.net/problem/9093

 

#include<bits/stdc++.h>

using namespace std;

int n;



int main(){
    cin >> n; //테케
    
    cin.ignore();

    while(n--){
        string s;
        getline(cin , s);
        stack<char> stk;
        
        for(auto c : s){
            if(c != ' '){
                stk.push(c);
            }else{
                while(!stk.empty()){
                    cout << stk.top();
                    stk.pop();
                }
                cout << c;
            }
        }
        while(!stk.empty()){
                    cout << stk.top();
                    stk.pop();
        }cout << '\n';
        
    }
    
    
    return 0;
}

 

여기서 어떤 개념이 쓰였을까.

 

확장 3 개념이 쓰였다.

다시 말해서 연속으로 원소를 집어넣고 다시 뺀다면 역순으로 나오게 되는 것이다.

 

여기서 더 생각해야할 점은

문자열을 다 넣는 것이 아니라

단어별로 넣는 것이다.

abc def => cba, fed지

fed cba가 아니란 말이다.

 

 

---

 

다음은 

2. 괄호

이것도 어려운 문제다.

https://www.acmicpc.net/problem/9012

 

#include <iostream>
#include <stack>


int main() {
    
    int N;
    
    std::cin >> N;

    for(int i = 0; i < N; i++) {
        std::stack<char> stk;
        bool check = true;
        std::string str;
        std::cin >> str;
        int len = (int)str.length();
        for(int i = 0; i<len; i++) {
            char c = str[i];
            if(c == '('){
                stk.push(c);
            }else{
                if(!stk.empty()){
                    stk.pop();
                }else{
                    check = false;
                    break;
                }
            }
        }
        if(!stk.empty()){
            check = false;
        }
        if(check){
           std::cout << "YES\n";
        }
        else{
           std::cout << "NO\n";
        }
    }
}

 

어렵게 풀었지만

여기서 사용된 개념은 무엇일까?

 

역시 3번이다.

가장 최근에 넣은 것을 고르는 것이다.

?? 왜 그게 상관있는데?

( 이게 여는 괄호고 )가 닫는 괄호라 한다면

닫는 괄호는 가장 가까이에 있으면서 다른 닫는 괄호의 짝이 아닌 여는 괄호와 짝을 짓는다.

( ( ) )   , {1,2,3,4} 라고 괄호에 번호를 매기면

3번 괄호의 짝은 가장 가까우면서 다른 닫는 괄호의 짝이아닌 2번과 짝을 짓고

4번은 가장 가까운 2번이지만 이미 다른 닫는 괄호의 짝이라 제외하고 1번과 가장 가까우므로 짝을 짓게 된다.

 

다시 말해서. 우리는 (, 여는 괄호를 통해서 닫는 괄호를 만나면 짝을 지어주면 되는 것이다.

그리고 그게 되는 이유는 짝을 지어준 괄호를 꺼내주어 사라지기 때문에 뒤에 있는 괄호가 또 찾게 되는 것이다.

 

 

---

 

다음은

3. 스택 수열

https://www.acmicpc.net/problem/1874

 

#include <iostream>
#include <stack>
#include <vector>
#include <queue>

using namespace std;

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //1~N까지
    int N;
    cin >> N;
    
    stack<int> stk;
    vector<char> v;
    queue<int> q;
    
    //만들 수열
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        q.push(n);
    }


    //1~N까지 탐색하면서 만들 수 있는지 체크
    for (int i = 1; i <= N; i++) {
        stk.push(i);
        v.push_back('+');
        
        //스택에 넣은 숫자로 만들 수 있는지 체크한다.
        //뺄 수 있는 한 계속 뺀다.
        while (!stk.empty() && stk.top() == q.front()) {
            stk.pop();
            q.pop();
            v.push_back('-');
        }
    }
    
    //다 뺐다면 만들 수 있음.
    if (stk.empty()) {
        for (char c : v) {
            cout << c << '\n';
        }
    }
    else { //못만듬
        cout << "NO";
    }

}

이것도 어렵다.

여기서 어렵다는 건 문제를 푼다는 것이 아니라

스택을 이해한다는 것을 말한다.

 

저건.. 옛날에 푼거고 스택의 의미처럼 풀려면 아래처럼 풀어야 한다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    stack<int> s;
    int n;
    string ans;

    cin >> n;
    int m = 0;

	//n개의 숫자
    while (n--) {
        int x;
        cin >> x;
        //만드려는 숫자 x가 m보다 크면
        if (x > m) {
        	//x까지 집어넣어줘야함.
            while (x > m) {
                s.push(++m);
                ans += '+';
            }
            //스택의 맨 위 숫자가 x가 되었으므로 뺀다.
            s.pop();
            ans += '-';
        } else {
            //만드려는 숫자 x가 이미 스택에 들어있다면
            //다시 말해서 이미 넣었던 숫자라면 빼서 버렸는지 아니면 남았는지 체크해본다.
            bool found = false;
            //스택 전부 뒤진다.
            if (!s.empty()) {
                int top = s.top();
                s.pop();
                ans += '-';
                //찾았으면 계속 진행가능하다.
                if (x == top) {
                    found = true;
                }
            }
            //못찾으면 만들 수 없다.
            if (!found) {
                cout << "NO" << '\n';
                return 0;
            }
        }
    }
    for (auto x : ans) {
        cout << x << '\n';
    }
    return 0;
}

 

여기서도 무엇이 쓰였을까?

3번 개념이 쓰였다.

또한 1번도 쓰였다.

그래서 우리는 스택을 모두 뒤진 것이다.

스택에서 Random Access가 가능했다면 모두 뒤질 필요는 없었을 것이다.

 

 

---

 

 

마지막으로 스택인지 몰랐는데

스택인.. 문제다.

나만 몰랐었나보다.

https://www.acmicpc.net/problem/1406

1406번: 에디터

#예전 풀이

#include<iostream>
#include<list>

using namespace std;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    list<char> L;
    string s;
    cin >> s;
    
    for(auto c : s){
        L.push_back(c);
    }
    int N;
    cin >> N;
    
    auto t = L.end();
    
    
    for(int i = 0; i< N; i++){
        char cmd; // 명령어
        cin >> cmd;
        
        if( cmd == 'L'){
            if(t != L.begin()){
                t--;
            }
        }
        else if(cmd == 'D'){
                if(t != L.end()){
                    t++;
                } 
        }
        else if(cmd == 'B'){
            if(t != L.begin()){
                t--;
                t = L.erase(t); 
            }
        }
        else{ // P
            char add;
            cin >> add;
            L.insert(t, add);
         }

    }
    
    for(auto i : L){
        cout<<i;
    }
    
}

 

 

부끄럽다.

이번 풀이는 스택이다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
string s;

int main() {
    cin >> s;
    stack<char> left, right; //커서의 왼쪽 스택, 오른쪽 스택
    int n = s.size(); //문자열 사이즈
    
    //가장 처음에는 커서가 가장 오른쪽에 있고, 왼쪽 스택에 모든 원소가 들어있음
    for (int i=0; i<n; i++) {
        left.push(s[i]);
    }
    
    //m개의 명령
    int m;
    scanf("%d",&m);
    while (m--) {
        char what;
        scanf(" %c",&what);
        //커서 Left shift
        if (what == 'L') {
            if (!left.empty()) {
                right.push(left.top());
                left.pop();
            }
        } 
        //커서  right shift
        else if (what == 'D') {
            if (!right.empty()) {
                left.push(right.top());
                right.pop();
            }
        } 
        //커서 왼쪽 delete => 지울 원소가 있다면
        else if (what == 'B') {
            if (!left.empty()) {
                left.pop();
            }
        } 
        //커서 오른쪽 문자 추가 
        else if (what == 'P') {
            char c;
            scanf(" %c",&c);
            left.push(c);
        }
    }
    
    //left 상태를 모두 right에 옮겨서 결과 출력
    while (!left.empty()) {
        right.push(left.top());
        left.pop();
    }
    while (!right.empty()) {
        cout << right.top();
        right.pop();
    }
    cout << "\n";
    return 0;
}

 

여기서는 어떤 개념이 쓰였을까?

커서의 위치가 연속적으로 변한다는 점에서

다시 말해서

커서의 위치에서만 변화가 일어난다는 점에서

1번 개념의 확장이라고 할 수 있다.

무엇인가 Push, Pop이 한군데에서만 일어난다? 

스택을 생각하자

 

---

 

 

더 많은 스택의 문제가 있다.

 

https://www.acmicpc.net/problem/17413

 

 

---

https://www.acmicpc.net/problem/10799

 

 

 

---

 

https://www.acmicpc.net/problem/17298

 

 

 

 

---

 

https://www.acmicpc.net/problem/17299