알고리즘 스터디 4일차

창고지기·2025년 6월 26일

알고리즘스터디

목록 보기

4/22

박경록 저자님의 코딩 테스트 합격자 되기 c++ 편을 완독 하는 것을 목표로 남기는 공부 일지
(스택)

1. 짝지어 제거하기

1) 문제

문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.

2) 문제 분석 및 풀이

1) 설계, 분석

입력이 $10^6$ 이므로 $O(NlogN)$ 까지는 안전
스택을 활용하여 해결
- 스택 상단의 문자와 동일하면 pop()
마지막으로 스택이 비어있는지 여부 반환
$O(N)$

2) 풀이

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

using namespace std;

int solution(string s)
{
    stack<char> st;
    int answer = -1;

    for (int i=0; i < s.size(); i++)
    {
        if (st.empty())
        {
            st.push(s[i]);
            continue;
        }

        if (st.top() == s[i])
        {
            st.pop();
        }
        else
        {
            st.push(s[i]);
        }
    }

    answer = st.empty() ? 1 : 0;

    return answer;
}

2. 후위 표기식

1) 문제

문제 설명
수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 $a+b$ 는 전위 표기법으로는 $+ab$ 이고, 후위 표기법으로는 $ab+$ 가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 $a+b*c$ 를 후위 표기식으로 바꾸면 $abc*+$ 가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 $a+b*c$ 는 $(a+(b*c))$ 의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 $*$ 를 괄호 밖으로 꺼내게 되면 $(a+bc*)$ 가 된다. 마지막으로 또 $+$ 를 괄호의 오른쪽으로 고치면 $abc*+$ 가 되게 된다.

입력
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, , /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력
첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

2) 문제 분석 및 풀이

1) 설계, 분석

N = 100, 시간제한 = 2초 이니 시간 복잡도는 충분
연산자가 LIFO형태로 나오는 곳도 있고 아닌곳도 있음.
- 각 연산자 별로 우선순위가 있음.
- A+B*C-D/E => ABC*+DE/-
  - - 를 입력하는 시점에 연산자가 출력됨
  - 연산자를 출력하는 조건을 알아내기
- A * (B+C) => ABC+*
  - 괄호가 없어짐
- (A+B)*C => AB+C* (나만의 테스트 케이스)
  - 괄호가 없어지고 중간에 출력됨
연산자
- top이 현재 연산자보다 우선순위가 낮으면 삽입.
- top이 현재 연산자보다 우선순위가 같거나 높으면
  - pop 후 위 단계 반복.
  - 자신의 우선순위보다 낮은 연산자가 나올 때까지 반복
    - * / 의 경우 + - ( 가 나올 때까지
    - +- 의 경우 ( 가 나올 때까지
  - ( 의 경우 )와 짝지어 지는 특수한 경우라 가장 낮은 순위로 지정
괄호
- 여는 괄호는 스택에 삽입
- 닫는 괄호면 여는 괄호가 나올때까지 pop (3번 테스트 케이스)
일반 문자
- 바로 출력
$O(N)$

2) 풀이

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

void solution(const string& s)
{
  // 연산자 우선순위
  map<char, int> operatorPrecedence = {
    {'(',0},
    {'+',1},
    {'-',1},
    {'*',2},
    {'/',2},
  };

  stack<char> st;
  auto it = s.begin();
  while (it != s.end())
  {

    //0. 연산자인 경우
    if (*it == '+' || *it == '-' || *it == '*' || *it == '/')
    {
      // 스택이 비어 있으면 넣음
      if (st.empty())
      {
        st.push(*it);
      }
      // 1. stack 맨위의 연산자가 우선 순위가 높은 경우
      else if (operatorPrecedence[st.top()] >= operatorPrecedence[*it])
      {
        // 맨위의 연산자보다 자기의 연산자가 커질때까지
        while( !st.empty() && operatorPrecedence[st.top()] >= operatorPrecedence[*it])
        {
          cout << st.top();
          st.pop();
        }
        st.push(*it);
      }
      else 
      {
        st.push(*it);
      }

    }
    //1. 괄호인 경우
    else if (*it == '(' || *it == ')')
    {
      if (*it == '(') st.push(*it);
      else if (*it == ')')
      {
        while (st.top() != '(')
        {
          cout << st.top();
          st.pop();
        }
        st.pop();
      }

    }
    //2. 일반 문자일 경우
    else 
    {
      // 바로 출력
      cout<<*it;
    }
    ++it;
  }

  while (!st.empty())
  {
    cout << st.top();
    st.pop();
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  string s;

  cin.tie(0);
  cin >> s;

  solution(s);
}