[백준 1406] 에디터

🔗알고리즘 문제

연결 리스트를 이용하여 쉽게 풀 수 있는 문제였다. 최근에 자료구조 수업시간에 배운 연결 리스트를 문제를 푸는데 사용하여 더 잘 이해한 기분이었다.

문제 분석

간단히 말해 주어진 문자열을 명령에 맞게 처리한 후 처리된 문자열을 출력하면 되는 문제이다.

이때 명령들은 다음과 같다.

L : 커서를 왼쪽으로 한 칸 옮긴다. * 이 때 커서가 맨 앞이라면 무시
D : 커서를 오른쪽으로 한 칸 옮긴다. * 이 때 커서가 맨 뒤라면 무시
B : 커서 왼쪽에 있는 문자를 삭제한다. * 이 때 커서가 맨 앞이라면 무시
P a : a문자를 커서 왼쪽에 추가한다.

발상

이 문제는 커서를 이리저리 옮겨다니며 해당 커서 위치에 값을 추가 / 삭제하는 연산을 요구하는 문제이다.

시간제한을 맞추기 위해서는 삽입/삭제에서 O(1)의 시간복잡도를 가지는 연결 리스트를 사용해야겠다고 생각하였다.

Iterator를 사용하여 커서 위치를 옮기며 문제를 해결하였다.

알고리즘 설계

1. 문자열을 입력하고 연결 리스트에 순서대로 담아준다.
   ㄴ 처음 커서의 위치는 리스트의 end위치로 한다.
2. 명령을 입력받고 처리한다.
3. 처리 완료된 문자열을 출력한다.

코드

#include<iostream>
#include<list>
#include<string>

using namespace std;

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

    list<char> clist;
    string input;

    cin >> input;

    for(int i = 0; i < input.length(); i++)
        clist.push_back(input[i]);

    list<char>::iterator iter = clist.end();
    int cnt;

    cin >> cnt;

    for(int i = 0; i < cnt; i++){
        char order;
        char cinput;

        cin >> order;

        switch(order){
        case 'L':
            if(iter != clist.begin())
                --iter;
        break;
        case 'D':
            if(iter != clist.end())
                ++iter;
        break;
        case 'B':
            if(iter != clist.begin()){
                --iter;
                iter = clist.erase(iter);
            }
        break;
        case 'P':
            cin >> cinput;
            clist.insert(iter, cinput);
        break;
        }
    }

    for(iter = clist.begin(); iter != clist.end(); ++iter){
        cout << *iter;
    }
}