백준 1360번: 되돌리기 [C++]

작성일 | In
골드 V 골드 V

문제

되돌리기
간단하지만 어려워보이는 구현 문제입니다.

풀이

type은 그냥 구현하면 되고, undo를 구현하는게 조금 까다롭습니다.
undo를 했던 행동을 순서대로 취소하는 것이라 생각하지 말고, 다시 시간을 되돌린다고 생각하면 편합니다.
시간을 key로 하고 그때 text를 value로 하는 map을 내림차순으로 하나 만들어줍니다.
그럼 upper_bound를 통해 시간을 되돌렸을 때 text를 쉽게 찾을 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;


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

    map<int, string, greater<>> textByTime;
    textByTime.insert({0, ""});

    string text;
    int n;
    cin >> n;
    while (n--) {
        string cmdType;
        cin >> cmdType;

        if (cmdType == "type") {
            string value;
            int time;
            cin >> value >> time;
            text += value;
            textByTime.insert({time, text});
        } else {
            int undoTime, time;
            cin >> undoTime >> time;
            auto iter = textByTime.upper_bound(time - undoTime);
            text = iter == textByTime.end() ? "" : iter->second;
            textByTime.insert({time, text});
        }
    }

    cout << text;
}

백준 1360번: 되돌리기 [C++]