#1406: 에디터
문제:
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
| L | 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) |
| D | 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) |
| B | 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) / 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임 |
| P $ | $라는 문자를 커서 왼쪽에 추가함 |
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력:
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.
풀이:
- 처음 이 문제를 풀 때 커서를 int 값으로 계속 track하면 된다고 생각하고 string.insert 같은 함수를 이용하여 풀었는데 시간 초과로 계속 틀렸다. 그러던 와중 같은 문제를 풀은 스터디 친구가 스택을 2개 사용한다는 힌트를 주었다.
- 우선 이 문제는 커서를 기준으로 왼쪽 스택 한개 오른쪽 스택 한개로 하여 풀면 된다. 이것만 알면 구현하는 것은 어렵지 않다. 처음 시작 할 때 커서는 제일 오른쪽에 있으므로 처음 받은 string 값을 왼쪽 스택에 모두 넣어준다.
- 그 다음 커서를 옮길 때 마다 커서가 움직이는 방향에 맞게 값을 push 해주고 pop 해주면 된다. 지울 때는 왼쪽을 지워야 하니 왼쪽 스택에서 pop해주면 된다. 넣을 때는 반대로 문자열을 받고 push해주면 된다. 오히려 스택이 처음 이용했던 string.insert로 맞는 index에 넣는 방식보다 구현하기 쉬웠다.
- 마지막에 출력할 때는 오른쪽 스택에 넣어주면 top하는 순서가 거꾸로 되어 나오지 않고 순서대로 나온다. 따라서 오른쪽 스택에 왼쪽에 있던 모든 값을 넘겨주고 오른쪽 스택을 모두 프린트 해줘야 된다.
⚠️ 여기서 주의 해야 할 점은 for loop에서 stack.size()를 이용할 때 stack을 pop할 때마다 stack.size()값이 줄고 있다는 점이다. 따라서 for loop전에 크기를 기록하여 모두 빼주어야 된다.
⚠️ #9012: 괄호에서 이야기 했던 것처럼 stack.top()을 이용할 때는 empty인지 우선적으로 확인해주어야 되는 것을 잊지 말아야 한다.
코드:
#include <iostream>
#include <stack>
using namespace std;
int main(){
int n;
stack<char> left, right;
string s = "";
getline(cin, s);
cin >> n;
//모든 문자열들 왼쪽 스택에 넣기
for(int i = 0; i < s.size(); i++) left.push(s[i]);
for(int i = 0; i < n; i++){
char temp;
cin >> temp;
if(temp == 'L'){
if(!left.empty()){
//왼쪽으로 넘어가지 왼쪽에 있던 값이 오른쪽으로 스택으로 가야 됨
right.push(left.top());
left.pop();
}
}
else if(temp == 'D'){
//위의 경우와 반대
if(!right.empty()){
left.push(right.top());
right.pop();
}
}
else if(temp == 'B'){
if(!left.empty()) left.pop();
}
else if(temp == 'P'){
char letter;
cin >> letter;
left.push(letter);
}
}
//스택 사이즈가 줄어드는 것을 방지하기 위해 값을 저장
int left_size = left.size();
//출력 시 편하게 모든 문자들 오른쪽 스택으로 옮기기
for(int i = 0; i < left_size; i++){
right.push(left.top());
left.pop();
}
//위와 마찬가지로 스택 사이즈가 줄어드는 것을 방지하기 위해 값을 저장
int right_size = right.size();
for(int i = 0; i < right_size; i++){
cout << right.top();
right.pop();
}
}
Leave a comment