[백준 C++] 9935번 문자열 폭발

문자열 폭발

9935번: 문자열 폭발

 

자료 유형 : 스택인 줄 알았지만 문자열을 다루는 것이 핵심

 

문자열과 함께 나도 폭발했다. 수 차례 WA를 받고 주먹구구 식으로 코드를 고쳐나가는 내 모습이 비참했다.

 

문자열과 폭발 문자열이 주어진다. 문자열에 폭발 문자열이 포함되어 있다면 해당 문자열을 폭발시키고, 남아 있는 문자열을 합친다. 이 작업을 반복해서 더 이상 폭발시킬 문자열이 없다면 남아있는 문자열을 출력한다. 만약 남아있는 문자열이 없다면 "FRULA"를 출력한다.

 

문제를 읽고 스택을 써야겠다는 생각이 강하게 들어 문제를 오히려 복잡하게 해결해버렸다. 심지어 시간 초과가 나서 스택을 없애고 벡터로 문제를 해결했다.

 

다음과 같은 논리로 문제를 해결했다.

 

1. order라는 배열을 만들었다. 숫자와 소문자, 대문자 모두 넣을 수 있도록 넉넉하게 만들었다. 폭발 문자열이 등장하는 순서를 나타내기 위함이다. 예를 들어, 폭발 문자열 exp가 "abc"라면 order[exp[0] - '0'], order[exp[1] - '0'], order[exp[2] - '0']을 각각 1, 2, 3으로 설정한다. 문자열 str을 조회하다가 order[str[n] - '0'], order[str[n + 1] - '0'], order[str[n + 2] - '0'], 이 1, 2, 3의 순서로 등장한다면 폭파시키기 위함이다.

 

2. 폭발 문자열의 길이가 1인 경우는 str을 탐색하면서 exp와 다른 것을 ans에 더한다.(ans는 마지막 부분에서 FRULA를 출력해야 하나 여부를 결정할 때 쓰인다)

 

3. 지금부터는 폭발 문자열의 길이가 2 이상인 경우다.

 

4. (Case 1)먼저 str을 탐색하다가 폭발 문자열의 첫 번째 원소와 같은 것을 발견했을 때다. 이 때는 벡터에 넣는다.

 

5. (Case 2) 두 번째는 str[i]가 폭발 문자열의 첫 번째 원소는 아니지만 올바른 순서일 때다. 예를 들어, 폭발 문자열 "abc" 중 a가 이미 벡터에 들어가 있고 바로 다음으로 b가 나왔다면 b는 올바른 순서다(올바른 순서인지 판단하는 idx라는 변수가 있다). 이 경우에도 벡터에 넣는다. 다만, 마지막 폭발 문자열까지 올바르게 있다는 것을 확인했다면 벡터에서 마지막에 위치해 있는 폭발 문자열을 제거하고, idx를 조정한다.

 

6. (Case 3) Case 1, Case 2가 아니라면 지금까지 벡터에 모아둔 원소들은 모두 쓸모 없어진다. 벡터의 원소들을 모두 ans에 더한다.

 

7. 반복문을 마친 후 벡터에 남아있는 것이 있을 수 있으므로 벡터의 원소들을 모두 ans에 더한다.

 

8. ans가 empty string이라면 "FRULA"를 출력하고, 그렇지 않다면 ans를 출력한다.

 

#include <iostream>
#include <vector>
#include <string>
#define FOR(i, N) for (int i = 0; i < N; i++)
using namespace std;
int order[80];
vector<char> s;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  string str, exp, ans, tmp;
  cin >> str >> exp;
  int idx = 1, strSize = int(str.size()), expSize = int(exp.size());
  FOR(i, expSize) order[exp[i] - '0'] = idx++;
  idx = 1;
  if (expSize == 1) {
    FOR(i, strSize) {
      if (str[i] != exp[0]) ans += str[i];
    }
  } else {
    FOR(i, strSize) {
      if (order[str[i] - '0'] == 1) {
        // Case 1 : 폭발 문자열의 첫 번째 원소일 경우
        s.push_back(str[i]);
        idx = 2;
      } else if (order[str[i] - '0'] == idx) {
        // Case 2 : 폭발 문자열의 idx 번째 원소일 경우
        if (idx == expSize) {
          FOR(i, expSize - 1) s.pop_back();
          if (s.empty()) idx = 1;
          else idx = order[s.back() - '0'] + 1;
        } else {
          s.push_back(str[i]);
          idx++;
        }
      } else {
        // Case 3 : 이도저도 아닌 경우
        idx = 1;
        for (auto &el : s) tmp += el;
        s.clear();
        ans += tmp;
        ans += str[i];
        tmp = "";
      }
    }
  }
  for (auto &el : s) tmp += el;
  ans += tmp;
  if (ans.empty()) ans = "FRULA";
  cout << ans << '\n';
}

 

너무 복잡하게 푼 것 같아서 다른 분의 코드를 재구성해봤다. (* 실제로 제출해본 것은 아니므로 아래 코드로 통과한다는 보장은 없음)

 

이 코드는 다음과 같은 논리로 문제를 해결한다.

 

1. 문자열 str은 탐색하는 도중에 result 배열에 넣는다. 그러다가 bomb[bombSize - 1]과 같은 문자를 만난다면 그 이전 bombSize개의 문자열이 bomb와 같은지 확인한다 bomb와 같다면 index를 조정함으로써 삭제하고, 그렇지 않다면 그대로 둔다.

 

2. result의 크기가 0이라면 "FRULA"를 출력하고, 그렇지 않다면 result를 출력한다.

 

#include<iostream>
#include<string>
using namespace std;
#define MAX_SIZE 1000001

string str;
string bomb;
char result[MAX_SIZE];

int main() {
  ios::sync_with_stdio(false);
  cin >> str >> bomb;

  int strSize = int(str.size());
  int bombSize = int(bomb.size());
  int index = 0;
  bool flag;

  for (int i = 0; i <= strSize; i++) {

    result[index++] = str[i];

    if (result[index - 1] == bomb[bombSize - 1]) {

      flag = true;
      for (int j = 0; j < bombSize - 1; j++) {
        if (result[index - bombSize + j] != bomb[j]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        index = index - bombSize;
      }
    }
  }

  if (strlen(result) == 0) cout << "FRULA";
  else cout << result;
}