[백준 1360] 되돌리기

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

1360번: 되돌리기

최근 기업들의 코딩테스트를 진행해보면 문자열 관련 문제가 많이 보이는 것을 알 수 있습니다.

이러한 경향에 따라 문자열 문제 관련한 글을 적어보려 합니다.

 

그러나 실제 이 문제에서는... 문자열을 깊게 쓰지않고 쉬운 수준의 문제입니다.

그래도 최근 워낙 PS 카테고리를 다루지 않았기에 새로운 쓸 겸 적어보겠습니다.

 

읽어보시면 type 실행은 쉽게 이해할 수 있을겁니다.

그러나 저는 처음 문제를 읽을 때 undo 실행 관련한 내용을 쉽게 이해하지 못했습니다.

undo 한 것을 undo한다....되돌린 것을 다시 되돌린다.....이해하기 힘든 표현이였습니다.

그러나 결론은 간단했습니다.

복잡한 것은 생각하지 않고 각 명령이 들어올때마다 벡터에 해당 시간과 문자를 저장하고 undo 명령시 (현재 시간 - t)초 이전의 상태를 불러오면 됩니다.

 

또한 초는 10^9까지 주어진다고 했으나 명령의 개수 N이 100이하밖에 안되기 때문에 메모리나 시간복잡도에 대한 고민도 할 필요가 없었습니다.

 

그림으로 보시면 직관적으로 이해가 가능하실겁니다.

 

명령	type a 1	type b 2	undo 2 3	undo 2 4
index	0	1	2	3
값	{"a",1}	{"ab",2}	{"",3}	{"a",4}

 

type 명령어는 그냥 뒤에 문자를 붙이면 됩니다.

그리고 위의 그림처럼 undo명령어 일 때 배열을 뒤부터 순서대로 탐색하며 (현재시간-t)초 이전의 상태를 불러오면 됩니다.

그러므로 2번 index의 값은 (3-2) 즉 1초 이전의 시간에서의 값을 불러오면 됩니다. 그러나 1초 이전 즉 0초의 값은 존재하지 않기에 공백입니다.

그리고 3번 index의 값은 (4-2) 즉 2초 이전의 시간에서의 값을 불러오면 됩니다. 그러므로 2초 이전에서 갱신된 1초에서의 값을 불러왔기에 "a"입니다.

 

제가 만든 다른 예시입니다.

명령	type a 100	type b 200	undo 90 300	undo 200 301
index	0	1	2	3
값	{"a",100}	{"ab",200}	{"ab",300}	{"a",301}

 

undo 90 300에서 (300-90)=210초 이전의 값인 200초에서의 값을 꺼내왔기에 값은 ab입니다.

undo 200 301에서 (301-200)=101초 이전의 값인 100초에서의 값을 꺼내왔기에 값은 a입니다.

 

문제 자체는 쉬운 편이라고 생각합니다.

파싱도 포함되지 않을까라 생각했는데 개행을 주고 값을 주므로 그냥 순서대로 받으면 되기에 파싱이 없기에 더 쉽게 느껴진 것 같습니다.

 

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int N;
vector<pair<string,int>> ans;
string get_ans(int target_sec)
{
    for(int i=ans.size()-1;i>=0;i--)
    {
        if(target_sec>ans[i].second) return ans[i].first;
    }
    return "";
}
int main()
{
    cin >> N;
    for(int i=0;i<N;i++)
    {
        string cmd,val; int sec;
        cin >> cmd >> val >> sec;
        if(cmd == "type") 
        {
            string push_val;
            if(ans.size())push_val = ans.back().first+val;
            else push_val = val; 
            ans.push_back({push_val,sec});
        }
        else
        {
            ans.push_back({get_ans(sec-atoi(val.c_str())),sec});
        }
    }
    cout << ans.back().first;
}