스택 (Stack) 문제 유형

 

 

1.  괄호 쌍이나 문자 확인 유형 (기본 유형)

 

2.  오큰수 유형 (심화 유형)

 

3. 커서 이동 유형

 

4.  후위 표현식 유형

 

 

---

 

 

1.  기본 유형 : 괄호 쌍이나 문자 확인 유형

 

괄호 (실버 4) : https://www.acmicpc.net/problem/9012 

좋은 단어 (실버 4): https://www.acmicpc.net/problem/3986

문자열 폭발 (골드 4) : https://www.acmicpc.net/problem/9935

 

 

=> 괄호 혹은 문자의 순서, 규칙이 조건을 만족하는지 확인하는 유형.

=> 보통은 input을 스택안에 넣어두고, 들어오는 input에 따라 규칙이 맞으면 true 혹은 pop, 규칙이 틀리면 false 혹은 전부 pop.

=> 괄호쌍 : 스택을 하나 생성하고, input이 "(" 일 시 스택에 넣는다. input이 ")"일 시 스택에서 "("를 하나 pop한다. 만일 "("이 없는데 input이 ")"일 경우, 또는 마지막에 스택에 "("이 남았을 경우 false를 리턴.

 

 

 

괄호 문제의 예시 코드.

#include <stdio.h>
#include <iostream>
#include <stack>

using namespace std;

void isVPS()
{
  stack<char> s, input;
  char c, top;

  while ((c = getchar()) != '\n')
    input.push(c);

  while (!input.empty())
  {
    top = input.top();
    input.pop();

    if (top == ')')
      s.push(top);
    else
    {
      if (s.empty())
      {
        cout << "NO" << '\n';
        return;
      }
      s.pop();
    }
  }

  if (!s.empty())
  {
    cout << "NO" << '\n';
    return;
  }

  cout << "YES" << '\n';
  return;
};

int main(void)
{
  int N;
  char c;

  scanf("%d", &N);
  cin.ignore();

  while (N-- > 0)
  {
    isVPS();
  }

  return 0;
}

 

---

 

 

 

2.  오큰수 유형 (심화 유형)

 

오큰수 (골드 4) : https://www.acmicpc.net/problem/17298

오등큰수 (골드 3) : https://www.acmicpc.net/problem/17299

탑 (골드 5) : https://www.acmicpc.net/problem/2493

 

 

오큰수 : https://sanghoonly.tistory.com/17

 

=> 현재 들어오는 값과 스택의 top을 비교하여, 값을 넣거나 빼는 유형.

=> 오큰수의 인덱스를 넣는 스택 하나와, 오큰수를 담는 결과 배열을 하나 생성.

=> 수열을 순회하면서, 들어온 수보다 스택 맨 위의 값이 크면 stack에다 push. 

=> 작을 경우, while문 돌면서 스택 맨 위의 값이 현재 값보다 커질때까지 pop, stack에서 나온 인덱스를 바탕으로 결과 배열 값 갱신.

=> 수열 순회 종료 후, 스택에 남아있는 수를 pop 하면서, 인덱스에 해당하는 결과 배열 값을 -1로 수정.

 

 

 

예시 코드 (탑)

#include <iostream>
#include <stack>
#include <stdio.h>

using namespace std;

int main(void)
{
  int N, m;
  scanf("%d", &N);
  cin.ignore();

  int towers[N], received[N];
  stack<int> s;

  for (int i = 0; N > i; i++)
  {
    scanf("%d", &m);
    towers[i] = m;
  }

  for (int i = 0; N > i; i++)
  {

    if (s.empty())
    {
      s.push(i);
      received[i] = i;
    }
    else if (towers[s.top()] < towers[i])
    {
      while (!s.empty() && (towers[s.top()] < towers[i]))
        s.pop();
      received[i] = !s.empty() ? s.top() : i;
      s.push(i);
    }
    else
    {
      received[i] = s.top();
      s.push(i);
    }
  }

  for (int i = 0; N > i; i++)
  {
    if (received[i] == i)
      received[i] = 0;
    else
      received[i]++;
  }

  for (int i = 0; N > i; i++)
    cout << received[i] << ' ';
  return 0;
}

 

 

---

 

 

 

 

3. 커서 이동 유형

 

에디터 (실버 3) : https://www.acmicpc.net/problem/1406

키로거 (실버 3) : https://www.acmicpc.net/problem/5397

 

 

=> 커서가 존재하여, 오른쪽 또는 왼쪽으로 이동하며 추가 & 삭제하는 경우

=> 커서의 왼쪽 단어를 담는 left stack, 오른쪽을 담는 right stack의 두 개 스택이 필요.

=> 커서 왼쪽으로 이동시 -> left stack에는 right stack의 맨 위 요소를 push, 반대로 right에서는 pop.

=> 커서 오른쪽 이동시 -> 왼쪽 이동의 반대로 동작.

=> 글자 삭제시 -> left에서 pop.

=> 글자 추가시 -> left에 push.

 

 

예시 코드(에디터)

 

#include <iostream>
#include <stack>
#include <deque>

using namespace std;

int main(void)
{
  int N;
  char cmd, addChar;
  deque<char> left;
  deque<char> right;
  string str;

  getline(cin, str);
  cin >> N;

  for (int i = 0; str.size() > i; i++)
    left.push_back(str[i]);

  while (N-- > 0)
  {
    cin >> cmd;
    if (cmd == 'L')
    {
      if (left.empty())
        continue;
      right.push_back(left.back());
      left.pop_back();
    }

    if (cmd == 'D')
    {
      if (right.empty())
        continue;
      left.push_back(right.back());
      right.pop_back();
    }

    if (cmd == 'B')
    {
      if (left.empty())
        continue;
      left.pop_back();
    }

    if (cmd == 'P')
    {
      cin >> addChar;
      left.push_back(addChar);
    }
  }

  for (int i = 0; left.size() > i; i++)
    cout << left[i];
  for (int i = right.size() - 1; i >= 0; i--)
    cout << right[i];
  return 0;
}

 

 

 

---

 

 

4.  후위 표현식 유형

후위 표현식 2 (실버 3) : https://www.acmicpc.net/problem/1935

후위 표현식 (골드 4) : https://www.acmicpc.net/problem/1918

 

=> 중위 표현식을 후위 표기식으로 바꾸거나, 그 반대로 바꿈.

=> 혹은 답을 계산하라는 문제.

=> 스택을 이용하여, 숫자 혹은 문자를 담으면 됨.

=> 문자를 담는 경우, 연산 우선순위는 () > * or / > + or -

=> 스택 맨위 연산자보다 우선 순위가 같거나 낮은 연산자가 들어올 경우 -> 우선순위가 같다면 스택 맨 위에꺼 꺼내고 자기가 들어가기, 우선순위가 낮다면 같거나 높아질 때까지 pop

=> 스택 맨위 연산자보다 우선 순위가 높은 연산자가 들어올 경우 -> push.

=> 괄호의 경우: "(" : push. ")" : "(" 마주칠 때 까지 계속 stack을 pop.

 

예제 코드(후위 표현식)

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{

    string str;
    stack<char> oper;
    cin >> str;

    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] >= 'A' && str[i] <= 'Z')
        {
            cout << str[i];
        }
        else
        {
            if (str[i] == '(')
                oper.push(str[i]);
            else if (str[i] == '*' || str[i] == '/')
            {
                while (!oper.empty() && (oper.top() == '*' || oper.top() == '/'))
                {
                    cout << oper.top();
                    oper.pop();
                }
                oper.push(str[i]);
            }
            else if (str[i] == '+' || str[i] == '-')
            {
                while (!oper.empty() && oper.top() != '(')
                {
                    cout << oper.top();
                    oper.pop();
                }
                oper.push(str[i]);
            }
            else if (str[i] == ')')
            {
                while (!oper.empty() && oper.top() != '(')
                {
                    cout << oper.top();
                    oper.pop();
                }
                oper.pop();
            }
        }
    }
    while (!oper.empty())
    {
        cout << oper.top();
        oper.pop();
    }

    return 0;
}