백준[9935] - 문자열 폭발

문제

백준 9935 문제 보기

접근 방법

처음 vector의 erase를 활용해 문제를 풀었지만 시간 초과가 났다 erase에 같은 경우는 제거 요소 뒤에 있는 값을 땡기기 위해 다시 어느 정도의 시간을 소비하기 때문이다. 이에 다른 방법으로 정답 배열을 하나 두고 정답 배열에 값이 하나씩 저장 될때 마다 문자열을 검사하는 식으로 문제를 접근하면 해결됨을 찾아냈다.

코드

#include <iostream>
#include <string>

using namespace std;

int m, n;
char ans[1000001];
string s, ex;

bool isMatching(int s) {
    // 넘겨받은 인덱스부터 폭발 문자열 길이만큼 검사
    for (int i = s ; i < s + m ; ++i) {
        // 하나라도 다르면 false 리턴
        if (ans[i] != ex[i - s]) {
            return false;
        }
    }
    return true;
}

int main() {

    cin >> s >> ex;

    n = s.length();
    m = ex.length();

    int pos = 0;
    // 문자열 검사 길이
    for (int i = 0 ; i < n ; ++i) {
        // 정답 배열에 문자 하나 저장
        ans[pos] = s[i];
        // 포지션 증가
        pos++;
        // 문자가 폭발하는지 검사
        if (pos - m >= 0 && isMatching(pos - m)) {
            // 폭발했다면 다시 포지션 감소
            pos -= m;
        }
    }

    ans[pos] = '\0';

    if(!pos)
        printf("FRULA");

    cout << ans;
    return 0;
}