[1일 1알고] G5 1360 되돌리기

https://www.acmicpc.net/problem/1360

 

문제는 두 개의 명령(type, undo)를 통해 완성된 문자열을 구하는 것입니다.

 

이 때 undo 명령을 처리하는 것이 중요문제인데, undo를 통해서 다른 undo가 취소될 수 있기 때문에 이를 고려해야합니다.

---

풀이

저는 undo를 통해서 이전의 undo를 취소할 수 있기 때문에 간단하게 처리하기 위해서는 마지막 명령어부터 거슬러 올라가는 것이 편할 것이라고 생각했습니다.

 

만약 10초에 2초만큼 undo를 한다고 치면 8초까지의 명령을 무시해야하는데 역으로 처리하면 앞의 명령들에 대해 고려 자체를 할 필요가 없습니다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;

struct command
{
    command() {};

    command(string type, string& _c, int _t): c(_c), t(_t)
    {
        if (type == "undo")
        {
            isUndo = true;
        }
    }

    bool isUndo = false;
    string c;
    int t;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<command> commands(N);
    int undo_time = 0;
    for (int i = 0; i < N; ++i)
    {
        string type;
        string c; int t;
        cin >> type >> c >> t;
        
        commands[i] = command(type, c, t);
        undo_time = t;
    }
    ++undo_time;
    string result;
    for (int i = N - 1; i >= 0; --i)
    {
        if (undo_time <= commands[i].t)
            continue;
        if (commands[i].isUndo)
        {
            undo_time = commands[i].t - (stoi(commands[i].c));
        }
        else
        {
            result += commands[i].c;
        }
    }

    reverse(result.begin(), result.end());
    cout << result;
    return 0;
}

type에 대한 입력과 undo에 대한 입력을 함께 처리하고자 struct command를 만들었는데, 더 좋은 방법이 있을 것 같긴 합니다.

 

undo를 한다면 undo가 적용된 시간을 undo_time에 저장하고 이를 통해 undo_time 범위 내에 들어오는 명령은 무시합니다.

처리된 문자는 거꾸로 저장되었으므로 reverse를 통해 뒤집어줍니다.