백준 알고리즘 9935번 문제는 쉽게 접근하면 너무나도 쉽고,
어렵게 접근하면 너무나도 어렵다.
저번주에는 하루종일 풀었는데도 못풀었고,
오늘 다시 시도했을 땐 3분 만에 풀었다.
확실한 건, 스택을 활용하면 아주 쉽게 풀린다는 것이다.
문제 링크
https://www.acmicpc.net/problem/9935
문제 분류
문자열(string) 클래스
스택
자료구조
문제 해석
input은 두 줄이다.
첫번째 줄 제시 문자열에서
두번째 줄 폭발 문자열을 모두 찾아 제거하면 된다.
폭발문자열이 제거된 이후에 남아있는 폭발문자열도 거듭 제거해야한다.
처음 시도에는 폭발문자열이 모두 사라질 때 까지 루프를 돌렸는데, 이렇게 접근하면 당연히 시간초과가 날 수 밖에 없었다.
두 번째 시도에서는 제시 문자열을 순회하며 폭발문자열도 함께 순회를 했고, 폭발 문자열의 end 에 도달하면 제시 문자열을 폭발문자열만큼 삭제하였다. iterator 접근법을 취한 것인데, 삭제 후 iterator의 위치를 재조정해야하기때문에 여간 까다로운 일이 아니었다. 또한 aaaaaa/aa 입력과 같은 동일문자 반복 입력 케이스에서 오답이 났다.
오늘 세번째 시도에서는 stack 자료구조를 아주잘 활용하였다.
정답 문자열 스택을 하나 만들고,
제시 문자열을 한 글자씩 ans_str에 push한다.
마지막 n개 글자가 폭발문자열과 동일하면 n개 pop_back한다.
이 과정을 반복하였다.
시간초과 없이 깔끔히 통과하였다!
나의 코드
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
int n, m;
#define MAXN 1000000
string mystr;
string explode_str;
int len;
bool ends_with_expl(const std::string& str) {
if (len > str.size() || len != explode_str.size())return false;
return str.substr(str.size() - len, len) == explode_str;
}
int main(void)
{
cin >> mystr;
cin >> explode_str;
len = explode_str.size();
string ans_str;
string::iterator exp_iter = explode_str.begin();
for (string::iterator iter = mystr.begin(); iter != mystr.end(); ++iter) {
ans_str.push_back(*iter);
if (ends_with_expl(ans_str)) {
for (int i = 0; i < len; i++) ans_str.pop_back();
}
}
if( ans_str.empty()) cout << "FRULA";
else cout << ans_str << "\n";
return 0;
}
'Programming > Algorithm' 카테고리의 다른 글
[c++/알고리즘] BFS :: 너비우선탐색의 개념 (0) | 2025.04.06 |
---|---|
[c++] 백준 1753번 오답노트 :: 다익스트라 구현 (0) | 2025.04.06 |