https://www.acmicpc.net/problem/1406
문제
예제, 반례
2004 Olympiad Croatian Highschool Competitions in Informatics National Competition #1 - Juniors 2번
알고리즘 접근 방법
처음 풀이 : 물론 오답임
#include <iostream>
#include <string>
using namespace std;
string S; // 초기에 편집기에 입력되어 있는 문자열 (길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다.)
char result[600000];
int cursor, string_size;
// L: 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
void L(){
if (cursor != 0)
cursor--;
}
// D: 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
void D(){
if (cursor != string_size)
cursor++;
}
// B: 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
// 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
void B(){
if (cursor != 0){
result[--cursor] == ' ';
for (int i=cursor; i<string_size; i++){
result[i] = result[i+1];
string_size--;
}
}
}
// P x : x라는 문자를 커서 왼쪽에 추가함
void P(char x){
for (int i=string_size; i>cursor; i--){
result[i] = result[i-1];
}
result[cursor] = x;
cursor++;
string_size++;
}
// 결과 프린트
void print(){
for (int i=0; i<string_size; i++){
cout << result[i];
}
cout << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> S;
for (int i=0; i<S.length(); i++){
result[i] = S[i];
}
cursor = S.length();
string_size = S.length();
int M; // 입력할 명령어의 개수를 나타내는 정수
cin >> M;
string cmd; // 명령어
for (int i=0; i<M; i++){
cin >> cmd;
if (cmd.find('L') == 0){
L();
}
else if(cmd.find('D') == 0){
D();
}
else if (cmd.find('B') == 0){
B();
}
else if (cmd.find('P') == 0){
char x; // P x
cin >> x;
P(x);
}
}
print();
return 0;
}왜 .. 오답인지 모르겠지만 아마 시간 문제.. 인거같기도 하다 .. 테스트 케이스는 잘 . . 나오는데 . .
찾아보니 사람들은
<list> 나 <linked list> 또는 <stack> 이용해서 풀었더라 ..
stack 을 이용해봅시다
- 커서를 기준으로 왼쪽 stack, 오른쪽 stack을 선언한다.
- 문제 조건을 만족하면서, P일 경우 왼쪽 stack에 push
- L일 경우, 왼쪽 stack top을 오른쪽 stack으로 push
- R일 경우, 오른쪽 stack top을 왼쪽 stack으로 push
- D일 경우, 왼쪽 stack top을 pop
- 출력할 땐, 왼쪽 stack 전체를 오른쪽으로 push
- 오른쪽 stack 전체를 pop하면서 출력
풀이
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string S; // 초기에 편집기에 입력되어 있는 문자열 (길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다.)
cin >> S;
// 커서를 기준으로 왼쪽 stack, 오른쪽 stack을 선언한다.
stack<char> l;
stack<char> r;
for (int i=0; i<S.length(); i++){
l.push(S[i]);
}
int M; // 입력할 명령어의 개수를 나타내는 정수
cin >> M;
string cmd; // 명령어
for (int i=0; i<M; i++){
cin >> cmd;
// L: 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
if (cmd.find('L') == 0){
if (!l.empty()){
r.push(l.top());
l.pop();
}
}
// D: 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
else if(cmd.find('D') == 0){
if (!r.empty()){
l.push(r.top());
r.pop();
}
}
// B: 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
// 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
else if (cmd.find('B') == 0){
if (!l.empty())
l.pop();
}
// P x : x라는 문자를 커서 왼쪽에 추가함
else if (cmd.find('P') == 0){
char x; // P x
cin >> x;
l.push(x);
}
}
// 결과 프린트
while (!l.empty()) {
r.push(l.top());
l.pop();
}
while (!r.empty()) {
cout << r.top();
r.pop();
}
cout << '\n';
return 0;
}정리
ㅎ ㅏ ... 외않됬을까
