BOJ - 1406. 에디터

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

 

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력 1

abcd 3 P x L P y

예제 출력 1

abcdyx

예제 입력 2

abc 9 L L L L L P x L B P y

예제 출력 2

yxabc

예제 입력 3

dmih 11 B B P x L B B B P y D D P z

사용할 자료구조

커서를 기준으로 왼쪽을 담을 스택, 오른쪽을 담을 스택 두 개의 스택을 만들었습니다.

stack<char> left; stack<char> right;

풀이 과정

1. 처음 입력받는 문자열은 왼쪽 스택에 순차적으로 담아줍니다. (abcd 인 경우, top이 d 가 되어야함 ⇒ 커서는 명령어가 수행되가 전에 문장의 맨 뒤에 위치하고 있다고 문제에서 언급했기 때문)

for(int i=0;i<str.size();i++){ left.push(str[i]); }

1. 문제에서의 4가지 명령어

2-1) L : 커서를 왼쪽으로 한 칸 옮기게 되면 커서 기준의 오른쪽 부분은 오른쪽 스택으로 옮겨져야 합니다.

if(command=="L"){ if(!left.empty()){ right.push(left.top()); left.pop(); }

이 때, 문제에서 커서가 문장의 맨 앞이면 무시된다고 했기 때문에 반드시 if(!left.empty()) 조건을 추가해줘야합니다. ⇒ 추가 안할시 스택이 비었음에도 불구하고 top을 가져오려고 하기 때문에 에러가 발생

2-2) D : 커서를 오른쪽으로 한 칸 옮기게 되면 커서 기준의 왼쪽 부분을 왼쪽 스택으로 옮겨야 합니다.

if(command=="D"){ if(!right.empty()){ left.push(right.top()); right.pop(); } }

2-3) B : 커서 왼쪽에 문자를 삭제

if(command=="B"){ if(!left.empty()){ left.pop(); } }

2-2, 2-3도 마찬가지로 스택이 비었는지 안비었는지 검사

2-4) P + char : P가 입력되었을 경우, char를 입력받아 왼쪽 스택에 추가해줍니다.

if(command=="P"){ char ch; cin>>ch; left.push(ch); }

1. 문제에서 시간 제한이 0.3 초로 주어졌기 때문에 스택을 사용하여 결과를 출력해줘야합니다.

(스택은 top 에 있는 원소만 조회할 수 있으므로 O(1) 만큼 걸립니다.)

//한쪽 스택에 다 담은 다음에 top출력 //커서 왼쪽 스택을 커서 오른쪽 스택에 다 옮기기 while(!left.empty()){ right.push(left.top()); left.pop(); } //커서 오른쪽 스택에서 top 차례대로 출력 while(!right.empty()){ cout<<right.top(); right.pop(); }

시간 복잡도

4가지 연산 (L,D,B,P)를 하는데 모두 O(1) 만큼 걸리고, 답을 출력하는 과정에서도 O(1)만큼 걸립니다.

명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000) 인데 0.3초 안에 해결해야하므로 반드시 시간복잡도 O(1)로 해결해야하는 문제였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string str;
    cin>>str;
    int n;
    cin>>n;
    stack<char> left;
    stack<char> right;
    //처음엔 커서가 맨 끝에 있으므로 처음 str 모두 왼쪽에 삽입
    for(int i=0;i<str.size();i++){
        left.push(str[i]);
    }
    for(int i=0;i<n;i++){
        string command;
        cin>>command;
        if(command=="P"){
            char ch;
            cin>>ch;
            left.push(ch);
        }else if(command=="L"){
            if(!left.empty()){
                right.push(left.top());
                left.pop();
            }
        }else if(command=="B"){
            if(!left.empty()){
                left.pop();
            }
        }else if(command=="D"){
            if(!right.empty()){
                left.push(right.top());
                right.pop();
            }
        }
    }
    //출력할때 O(1)로 나오게끔 해야댐
    //한쪽 스택에 다 담은 다음에 top출력
    
    //커서 왼쪽 스택을 커서 오른쪽 스택에 다 옮기기
    while(!left.empty()){
        right.push(left.top());
        left.pop();
    }
    //커서 오른쪽 스택에서 top 차례대로 출력
    while(!right.empty()){
        cout<<right.top();
        right.pop();
    }

    return 0;
}