대엉코딩

www.acmicpc.net/problem/1406

1. 풀이방법

- 커서가 여러칸씩 뛰는 명령어는 없으므로 상대적으로 간단하였습니다.

- 저는 커서의 앞쪽은 VECTOR 커서의 뒤쪽은 STACK 을 이용하였습니다.

- 방법은 여러가지가 있을 것 같습니다 편하신대로...

- 커서를 왼쪽으로 옮길 때 커서의 뒤쪽이 되는 한 문자는 STACK에 푸쉬하고

- 커서를 오른쪽으로 옮길 때는 STACK에서 POP해 와서 다시 VECTOR에 넣는 식으로 하였습니다.

- 아마 시작할 떄의 커서의 위치가 맨 뒤쪽이라서 이러한 생각을 자연스럽게 하게된 것 같습니다.

2. 주의사항

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	vector<char> tmpc;
	stack<char> tmps;
	int cursor;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		tmpc.emplace_back(s[i]);
	}
	cursor = s.length();
	int n;
	cin >> n;
	while (n--) {
		char c;
		cin >> c;
		if (c == 'L') {
			if (cursor == 0) continue;
			else { //커서 뒤쪽은 스택으로 옮겨 놓음
				tmps.push(tmpc[cursor - 1]); tmpc.pop_back(); cursor--;
			}
		}
		else if (c == 'D') {
			if (tmps.empty()) continue;
			else {
				tmpc.emplace_back(tmps.top()); tmps.pop();
				cursor++;
			}
		}
		else if (c == 'B') {
			if (cursor == 0) continue;
			else {
				tmpc.pop_back();
				cursor--;
			}
		}
		else {
			char c;
			cin >> c;
			tmpc.emplace_back(c);
			cursor++;
		}
	}

	//출력부
	for (int i = 0; i < tmpc.size(); i++) {
		cout << tmpc[i];
	}
	while (!tmps.empty()) {
		cout << tmps.top();
		tmps.pop();
	}


	return 0;
}

vector는 오름차순 정렬 되어있어야합니다(이진탐색 기반이기 때문에)

* 벡터(Vector) 란 ?

- 배열의 확장 느낌으로서 시퀀스 컨테이너의 대표적인 자료구조이다.

-  동적배열과 유사하다

- 자료들(data)가 구조적으로 인접한 위치에 있기 때문에 접근이 쉽고 메모리를 효율적으로 관리가능하다

- 배열과 같이 index를 통한 요소(data) 접근이 가능하다 .(매우 편리, 접근이 용이)

- 만약 맨뒤에 삽입이 아닌 맨 앞이나 중간, 임의의 위치 등에 삽입을 하려고 하는 경우 다른 요소들도

  재조정을 해야 하기 때문에 느리다 (비 효율적)

- 임의의 위치에 삽입, 삭제 등이 많이 일어나는 경우 벡터보다는 리스트를 활용하는것이 효과적이다.

* 벡터 ADT

- at( x ) (index가 x인 위치의 자료형 리턴)

- set(int x, object o) (index x의 위치에 o라는 객체 assign)

- insert(int i, object o) (index i의 위체서 o라는 객체 삽입)

- erase(int i) (index i에 있는 객체 삭제)

- size() (vector 의 사이즈 리턴)

- empty() (비어있는지 확인 -bool)

- push_back(object o) (vector 맨 끝에 삽입)

* ADT 시간복잡도 분석

- at(i),  set(i,0)   ----> O(1) ( vector는 index로 접근 가능 하므로 at, set은 모두 직접 접근하여 O(1) 타임에 가능하다.

- insert(i,o)  ----> O(n) (임의의위치 i에 자료를 삽입하는 경우 원래의 i위치 부터 끝까지 있던 자료들을 모두 한칸씩 뒤로 밀린다.)

-erase(i)  ----> O(n) (역시 비슷한 느낌입니다 ---앞으로 땡겨줘야함 )

* 벡터 활용의 예

- 정렬된 객체들의 집합들을 관리 해야할 때

* 벡터의 구현

<잘못된 부분이 있을 수 있습니다>

<알려주시면 수정 하겠습니다>

기본 크기를 64(index) 로 하고 만약 입력을 받다가 이크기를 넘어가게 되면

배열의 크기를 두배로 늘리고 기존의 자료구조들을 모두 옮기는 식으로 구현하였습니다.