되돌리기
문제 해석
명령과 수행한 시간이 주어졌을 때, 마지막에 남은 텍스트를 구하는 문제입니다.
명령은 다음 두가지가 있습니다.
- “type c”: 현재 글의 가장 뒤에 문자 c를 추가합니다.
- “undo t”: 이전 t초동안 수행된 작업을 역순으로 되돌립니다.
설계(10)
범위가 적어 O(N^2)에 해결가능한 문자열 문제입니다.
저의 경우에 {이전 상태, 현재 상태, 현재 시간}을 저장하는 구조체를 사용하였습니다.
우선, 빈 문자열로 초기화해줍니다.
type c가 나오는 경우 prev에는 이전의 cur문자열을 저장해주고, cur에는 현재 prev문자열에 c를 추가해줍니다.
undo가 나오는 경우, cur과 prev에 이전 cur문자열을 우선 저장해줍니다.
그 후, 현재 시간 - 되돌리는 시간 <= 이전 시간이 될때까지 cur문자열에 이전 prev문자열을 갱신시켜줍니다.
구현(20)
코드
#include <iostream>
using namespace std;
#define MAXN 101
struct node{
string prev,cur;
int t;
node():prev(""),cur(""),t(0){}
};
node arr[MAXN];
int N;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1 ; i <= N; i++){
string s;
cin >> s;
if (s == "type"){
char tmp;
int time;
cin >> tmp >> time;
arr[i].prev = arr[i-1].cur;
arr[i].cur = arr[i].prev+tmp;
arr[i].t = time;
}
else{
int t,cur_t;
cin >> t >> cur_t;
arr[i].prev = arr[i].cur = arr[i-1].cur;
arr[i].t = cur_t;
for (int j = i-1; j >=1; j--){
if (cur_t-t<=arr[j].t){
arr[i].cur = arr[j].prev;
}
else break;
}
}
}
cout << arr[N].cur <<"\n";
return 0;
}
디버깅
undo가 나왔을 때, cur문자열에 이전 cur문자열을 저장하지 않는 실수를 하였습니다.
3 type a 1 type b 100 undo 1000 10000
위와 같은 반례를 생각해보면 마지막 시간의 바로 이전의 시간이 조건에 부합하지 않아서 cur값이 갱신되지 않습니다.
따라서, 먼저 cur값을 이전 cur값으로 갱신시켜줘야합니다.
제출결과
0 ms
마무리
문자열 처리 문제였습니다.
O(N^2)에 해결했지만 O(N)풀이도 있다고 합니다.