인프런 커뮤니티 질문&답변

안녕하세요, 강사님의 강의를 수강하며 코딩테스트를 준비하고 있는 수강생입니다.

강사님의 좋은 코드 설명과 양질의 코드로 항상 감사하게 생각하고 있는데요,

다름이 아니라 제가 5 - B 문제를 풀다가 질문이 생겨서 글을 올리게 되었습니다.

저는 해당 <문자열 폭발> 문제를 읽자마자 '아 여느 괄호 연쇄 폭발 문제랑 비슷하구나' 라는 생각이 들어서

스택으로 문제 풀이 가닥을 잡게 되었는데, 그 와중에 전과는 다르게 폭발하는 string의 길이가 길어 졌으니

매번 탐색을 해주어야겠다, 시간 복잡도도 괜찮을 것 같다! 라는 생각에 코드를 작성해봤습니다.

생각보다 정답 풀이가 저의 풀이와 비슷해서 기분도 좋았는데, 왠지 모르게 시간초과가 계속 발생합니다.

<질문>

어느 부분을 고치면 시간 초과를 없앨 수 있을까요?

그리고 이러한 시간 초과를 겪지 않으려면 어떤 코딩 방식을 지향해야할까요? (이건 개인적으로 지금 발생하고 있는 문제가 제 코드 작성 습관과 관련이 있디고 생각해서 적었습니다.)

#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<climits>
#include<algorithm>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  string str; cin >> str;
  string bomb; cin >> bomb;
  stack<char> s;

  int len = str.length();
  int bomb_len = bomb.length();

  for(int i = 0; i < len; i++) {
    char now = str[i];

    // 폭탄을 확인할 만큼 stack이 큰지 확인
    // 폭탄을 넣을 만큼 크지 않다면 그냥 stack에 문자 넣기
    if(s.size() >= bomb_len - 1 && now == bomb[bomb_len - 1]) {
      // 폭탄 글자 길이 만큼 스택에서 글자 우선 뽑기
      string token;
      token = token + now;

      for(int j = 1; j < bomb_len; j++) {
        token = token + s.top();
        s.pop();
      }

      reverse(token.begin(), token.end());

      // 뽑은 문자열이 폭탄 글자인지 확인
      // 폭탄이 아니라면 다시 넣어주고 폭탄이면 뺀 문자열 그냥 버림
      if(token != bomb) {
        for(int j = 0; j < bomb_len; j++) {
          s.push(token[j]);
        }
      }
    }
    else {
      s.push(now);
    }
  }

  if(s.empty()) {
    cout << "FRULA";
  } else {
    string answer;
    int ans_len = s.size();

    for(int i = 0; i < ans_len; i++) {
      answer = answer + s.top();
      s.pop();
    }

    reverse(answer.begin(), answer.end());
    cout << answer;
  }
}