문제
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ $라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.
출력
첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.
내 풀이)
#include <iostream>
#include <list>
using namespace std;
char editor[100005] = { 0 };
int main()
{
//문제
// 1. 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오.
// 입력
// 1. 영어 소문자로 이루어진 문자열 입력 100,000
// 2. 입력할 명령어 개수 입력 500,000
// 3. 명령어를 입력(P의 경우 어떤 글자를 받을지 입력 받아야함)
// 처리
// 1. list를 사용해 시간 복잡도를 줄인다.
//
// 출력
list<char> list1;
//100000
cin >> editor;
//100000
for (int i = 0; editor[i] != '\0'; i++)
{
list1.push_back(editor[i]);
}
int count = 0;
cin >> count;
//cout << *iter << endl;
//iter = list1.erase(iter); //마지막 요소 삭제함
//--iter;
//iter = list1.erase(iter);
//--iter;
//iter = list1.erase(iter);
//for (list<char>::iterator iter = list1.begin(); iter != list1.end(); ++iter)
//{
// cout << *iter << endl;
//}
//--iter;
//list1.erase(iter);
list<char>::iterator iter = list1.end(); //끝 주소를 받음
for (int i = 0; i < count; i++)
{
char input;
cin >> input;
if (input == 'L')
{
if (iter != list1.begin())
{
--iter; //이전 노드 주소를 받음
}
}
else if (input == 'D')
{
if (iter != list1.end())
{
++iter; //다음 노드 주소를 받음
}
}
else if (input == 'B')
{
if (iter != list1.begin())
{
iter = list1.erase(--iter); //특정 시점의 포인터 노드를 삭제함
}
}
else if (input == 'P')
{
char input_next;
cin >> input_next;
iter = list1.insert(iter, input_next); //특정 지점의 포인터 노드를 추가함
++iter;
}
}
for (list<char>::iterator iter = list1.begin(); iter != list1.end(); iter++)
{
cout << *iter;
}
}피드백
입출력 속도를 향상시킨다.
ios_base::sync_with_stdio 는 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생합니다.
ios_base::sync_with_stdio(false); 코드를 작성해줌으로써 동기화를 비활성화시켜줍니다.
이로 인해, c++만의 독립적인 버퍼가 생성되어 c의 버퍼와 병행하여 사용할 수 없게 되지만, 사용하는 버퍼의 수가 줄어들었기 때문에 실행 속도는 빨라지게 됩니다.
=> 알고리즘 풀때는 싱글쓰레드 환경이기 때문에, ios_base::sync_with_stdio(false)사용해도 무관
cin과 cout이 묶여있기 때문에 풀어줘야 한다.
C++에서는 기본적으로 cin, cerr 스트림과 cout 스트림이 묶여있기(tie) 때문에 입출력 동작을 하기전에 출력 스트림 버퍼를 플러쉬(flush)한다. 이 묶여있는 것을 해제하기 위해 cin 오브젝트의 함수 tie에 NULL을 넣음으로써 출력스트림과의 묶여있음을 해제한다.
다른 풀이 2)
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main()
{
//0. 입출력 속도를 향상시킨다.
/*ios_base::sync_with_stdio 는 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생합니다.
ios_base::sync_with_stdio(false); 코드를 작성해줌으로써 동기화를 비활성화시켜줍니다.
이로 인해, c++만의 독립적인 버퍼가 생성되어 c의 버퍼와 병행하여 사용할 수 없게 되지만, 사용하는 버퍼의 수가 줄어들었기 때문에 실행 속도는 빨라지게 됩니다.
=> 알고리즘 풀때는 싱글쓰레드 환경이기 때문에, ios_base::sync_with_stdio(false)사용해도 무관
cin과 cout이 묶여있기 때문에 풀어줘야 한다.
C++에서는 기본적으로 cin, cerr 스트림과 cout 스트림이 묶여있기(tie) 때문에 입출력 동작을 하기전에 출력 스트림 버퍼를 플러쉬(flush)한다. 이 묶여있는 것을 해제하기 위해 cin 오브젝트의 함수 tie에 NULL을 넣음으로써 출력스트림과의 묶여있음을 해제한다.
*/
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//1. 문자열을 입력 받는다.
string s;
cin >> s;
//2. 명령어의 개수를 입력 받는다.
int M;
cin >> M;
//3. 명령어를 처리한다.
list <char> lst(s.begin(), s.end());
list <char>::iterator cursor = lst.end();
//string::size_type cursor = s.size() - 1; //마지막 인덱스
//string::iterator cursor;
while (M--)
{
//3-1. 명령어를 입력 받는다.
char op;
cin >> op;
//3-2. 각 명령어에 맞게 실행한다.
switch (op)
{
case 'L':
if (cursor != lst.begin())
{
--cursor;
}
break;
case 'D':
if (cursor != lst.end())
{
++cursor;
}
break;
case 'B':
//문자을 지운후 커서 위치 업데이트 필요함
if (cursor != lst.begin())
{
--cursor;
cursor = lst.erase(cursor); //반복자는 무효화 될수 있기 때문에, 반환값을 받아야 한다.
}
break;
case 'P':
char param;
cin >> param;
cursor = lst.insert(cursor, param);
++cursor;
break;
}
}
//4. 출력
for (list<char>::iterator iter = lst.begin(); iter != lst.end(); iter++)
{
cout << *iter;
}
}다른 풀이 3) c++ stl 사용으로 구현
#include <iostream>
#include <list>
#include <algorithm>
#include <string>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
list<char> L;
list<char>::iterator cursor;
for(int i=0;i<s.size();i++){
L.push_back(s[i]);
}
// L.push_back('F');
cursor = L.end(); // pointing F
// cursor--;
int num;
cin >> num;
for(int i=0;i<num;i++){
char tmp;
cin >> tmp;
if(tmp == 'L'){
if(cursor != L.begin()) cursor --;
}
else if(tmp == 'D'){
if(cursor != L.end()) cursor ++;
}
else if(tmp == 'B'){
if(cursor != L.begin()){
// cout << "erase else!!\n";
cursor--;
cursor = L.erase(cursor);
}
}
else if(tmp == 'P'){
char tmp2;
cin >> tmp2;
L.insert(cursor,tmp2);
}
// for(auto j:L) cout << j;
// cout << "\n" << *cursor << "\n";
}
for(auto j:L) cout << j;
}다른 풀이 3) c언어로 구현
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node{
char data;
struct node* next;
struct node* prev;
}node;
void print(node* n){
node* temp = n;
temp=temp->next;
while(temp){
printf("%c",temp->data);
temp=temp->next;
}
printf("\n");
}
int main(){
node* head = (node*)malloc(sizeof(node));
head->data='!';
head->prev=head->next=NULL;
node* cur = head;
char t;
while((t=getchar())!='\n'){
node* newnode = (node*)malloc(sizeof(node));
newnode->data=t;
newnode->prev=cur;
newnode->next=NULL;
cur->next=newnode;
cur=newnode;
}
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
//print(head);
char c;
scanf(" %c",&c);
switch(c){
case 'L':{
if(cur->prev) cur=cur->prev;
break;
}case 'D':{
if(cur->next) cur=cur->next;
break;
}case 'B':{
if(cur->prev==NULL) continue;
node* del = (node*)malloc(sizeof(node));
del=cur;
cur=del->prev;
if(del->next) {
cur->next=del->next;
del->next->prev=cur;
del->prev=NULL;}
else{cur->next=NULL;}
free(del);
break;
}case 'P':{
char tmp;
scanf(" %c",&tmp);
node* newnode = (node*)malloc(sizeof(node));
newnode->data=tmp;
newnode->prev=cur;
if(cur->next){
newnode->next=cur->next;
cur->next->prev=newnode;
}else{
newnode->next=NULL;
}
cur->next=newnode;
cur=cur->next;
break;
}
}
}
head=head->next;
while(head){
printf("%c",head->data);
head=head->next;
}
}'알고리즘' 카테고리의 다른 글
| [백준 알고리즘 c++] 문제 21.스택 10828 (0) | 2022.09.02 |
|---|---|
| [백준 알고리즘 c++] 문제 20. 키로거 5397 (0) | 2022.09.02 |
| [백준 알고리즘 c++] 문제 18. 골드 바흐의 추측 9020 (0) | 2022.09.02 |
| [백준 알고리즘 c++] 문제 18. 베르트랑 공준 4948 (0) | 2022.09.02 |
| [백준 알고리즘 c++] 문제 17. 소수 구하기 에라토스테네스의 체 1929 (0) | 2022.09.02 |
