[백준] 1406 에디터

 

문제를 읽어보고 오자.

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

1406번: 에디터

 

이 문제는 스택으로 풀이하는 것과 양방향 링크드 리스트 기반 자료구조로 풀이할수 있다. 나는 스택으로 풀이하는 법은 잘 몰랐기에, 후자로 풀이했다.

 

문제 설명은 어렵지 않다. 하지만 저 위에 있는 시간 제한의 눈에 잘 보인다. 0.3초면은 비교적 촉박한 시간이다. 그리고 입력받을 명령어의 개수도 최대 50만개로, 많은 편에 속한다.

 

조건 생각

---

이러한 제한된 조건에 근거해서 링크드 리스트 기반의 자료형으로 풀이를 하기로 했다. 링크드 리스트 기반 + 인덱스 사용이 가능한 자료형은 c++에서 list가 가장 적절하지 않았나 싶다.

 

iter를 한 번의 명령마다 계속 좌우로 이동할 수 있게 해서 연산의 양을 최대한 줄였다. 처음 사용하는 list 자료형이기에, 여러가지 난관이 있었지만 특히 erase 함수를 사용할 때 많이 헷갈렸다. 삭제한 이후의 iter를 반환값을 통해 받아줘야 한다는 개념이 생소했다. list의 정리는 다음 링크에 해 두었다.

https://tre2man.tistory.com/242

C++ list 자료형 사용법

 

풀이 코드는 다음과 같다.

 

#include <bits/stdc++.h>
using namespace std;
 
/*
이 문제는 링크드 리스트가 적용되어 있는 자료 구조를 사용했다.
최대 60만개의 데이터를 한 번에 이동하기에는 시간이 너무 오래 걸린다.
list::erase 함수를 사용 시 맨 뒤에 있는 원소를 삭제 후, iter 연산이 불가능해진다.
왜냐하면 연속된 자료 구조가 아니여서 -- 연산으로 이전 원소로 이동하지 못한다.
erase 함수의 반환값을 이용하여 iter를 이동할 수 있다.
*/
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int num;
    char cmd, add;
    string temp;
 
    cin >> temp;
    list<char> l(temp.begin(), temp.end());
    auto idx = l.end();
    cin >> num;
    while (num--)
    {
        cin >> cmd;
        if (cmd == 'P')
            cin >> add;
        if (cmd == 'L' && (idx != l.begin()))
            idx--;
        else if (cmd == 'D' && (idx != l.end()))
            idx++;
        else if (cmd == 'B' && (idx != l.begin()))
            idx = l.erase(--idx);
        else if (cmd == 'P')
            l.insert(idx, add);
    }
    for (auto i = l.begin(); i != l.end(); i++)
        cout << *i;
    return (0);
}