[백준 1406] 에디터 (c++, stack활용)

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

1406번: 에디터

 

1. 문제 접근

처음에 문제를 접근했을 때는, 편집기의 내용을 vector에 입력하고, iterator를 통해 커서를 직접 움직이는 형태로 문제를 풀이하였다. 예제로 주어진 세가지 testcase는 모두 통과했지만, 결과적으로는 시간초과로 인한 실패.

 

이번 시간초과로 벡터에 대해서 공부하였는데, vector는 원소가 추가되어 메모리 확장이 필요할 때 아예 새로운 메모리 공간을 할당받아야하기 때문에 비효율적이라는 것을 알게되었다.

따라서 중간에서의 삽입/삭제가 빠른 list를 사용해볼까 하다가 다른분의 풀이를 보고 deque를 활용해보기로 하였다.

(세가지 자료구조에 대한 정리 https://studying404.tistory.com/35)

 

deque를 활용하는 방법은 바로 커서는 가만히 고정되어있고, 커서를 기준으로 왼쪽 deque와 오른쪽 deque에 담겨있는 원소가 이동하는 방법이다. (커서가 왼쪽 deque와 오른쪽 deque 사이에 있다고 생각하자.)

 

표로 표현하자면, abcd를 입력했을때의 모습이다.

cursorLeft	a	b	c	d
cursorRight

커서를 왼쪽에 x를 추가하면

cursorLeft	a	b	c	d	x
cursorRight

커서를 왼쪽으로 한 칸 움직이면

cursorLeft	a	b	c	d
cursorRight	x

커서 왼쪽에 y를 추가하면

cursorLeft	a	b	c	d	y
cursorRight	x

위와 같이 표현해볼 수 있다!

 

따라서 왼쪽 컨테이너(cursorLeft)에서는 뒤에서 삽입/삭제가 이뤄지고 오른쪽 컨테이너(cursorRight)에서는 앞에서 삽입/삭제가 이루어진다.

 

어떻게 구현할 지를 알면 코드로 나타내는 것은 어렵지 않다!

 

2. 코드 작성

#include <iostream>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    string str; int num; char order;
    cin >> str >> num;
    deque<char> cursorLeft; //커서를 기준으로 왼쪽에 담기는 내용
    deque<char> cursorRight;//커서를 기준으로 오른쪽에 담기는 내용
 
    for (int i = 0; i < str.size(); i++) {
        cursorLeft.push_back(str[i]);
    }
    for (int i = 0; i < num; i++) {
        cin >> order;
        if (order == 'L') {     //커서를 왼쪽으로 한칸 옮김
            //left의 back을 right의 front으로
            if (cursorLeft.empty() == false) {
                cursorRight.push_front(cursorLeft.back());
                cursorLeft.pop_back();
            }
                
            else
                continue;
        }
        else if (order == 'D') {//커서를 오른쪽으로 한칸 옮김
            //right의 front를 left의 back으로
            if (cursorRight.empty() == false) {
                cursorLeft.push_back(cursorRight.front());
                cursorRight.pop_front();
            }
            else
                continue;
        }
        else if (order == 'B') {//커서 왼쪽에 있는 문자 삭제
            if (cursorLeft.empty() == false)
                cursorLeft.pop_back();
            else
                continue;
        }
        else if (order == 'P') {//x라는 문자를 커서 왼쪽에 추가
            char input;
            cin >> input;
            cursorLeft.push_back(input);
        }
    }
    for (int i = 0; i < cursorLeft.size(); i++) {
        cout << cursorLeft[i];
    }
    for (int i = 0; i < cursorRight.size(); i++) {
        cout << cursorRight[i];
    }
    cout << endl;
    
 
    return 0;
}