BOJ 9935

29 Jan 2020 • ProblemSolving

문자열폭발

문제출처

1.설계(X)

  • 문제 해석

    • 폭발문자열을 모두 없애고 남은 문자열을 출력하는 문제입니다.
    • 폭발문자열을 포함하고 있는 경우, 모든 폭발문자열이 없어지고 남은 문자열을 합칩니다.
    • 폭발문자열이 없을 때까지 반복하며, 남은 문자열을 출력합니다. 빈 문자열이면 “FRULA”를 출력합니다.
    • 문자열길이 <= 10^6

  • 설계

    • O(N^2)형태로 구현을 하여서 시간초과가 났습니다.
    • 꾸준함님의 블로그를 통해 스택형태로 구성해야 하는 것을 알았습니다.

2.구현(X)

  • 코드
#include <iostream>
#include <string>
using namespace std;
#define MAXN 1000000

char result[MAXN];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s, target;
	cin >> s >> target;
	int idx = 0;
	for (int i = 0; i < s.length(); i++) {
		result[idx] = s[i];
		if (result[idx] == target[target.length() - 1]) {
			if (idx - target.length() < 0) continue;
			bool flag = true;
			for (int j = 0; j < target.length(); j++) {
				if (result[idx - j] != target[target.length() - j - 1]) {
					flag = false;
					break;
				}
			}
			if (flag) idx -= target.length();
		}
		
		idx++;
	}
	
	if (idx== 0) cout << "FRULA";
	else {
		for (int i = 0; i < idx; i++) {
			cout << result[i];
		}
	}
	return 0;
}

  • 디버깅

  • 제출결과

3.마무리

  • 쉽게 아이디어를 생각하지 못했습니다. 스택형태로 구성하지 않고 폭발물이 없어질 때까지 string에 담아 반복처리하여 시간초과가 났습니다.
 BOJ

Related Posts