문제 출처

1. 문제설명


L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ $라는 문자를 커서 왼쪽에 추가함


  • 문자열 하나가 주어지고, 해당 옵션에 따라 진행한다.
  • 최종적으로 남은 문자열을 출력하면 된다.



2. 알고리즘 설계

  • 첫 번째 접근
    • string의 erase, insert를 이용해 각각 B, P 구현
    • string의 함수 시간복잡도가 $O(N)$ 이므로 해당 문제에 적합하지 않다.
  • 두 번째 접근
    • 이 문제의 B, P 연산은 입력 크기에 따라
    • 각각 $O(1)$이 되어야 한다.



3. 로직

  • 참고로 처음 커서의 위치는 str.size()이다.
    • “abcd” 라면 d의 다음 위치가 커서의 위치가 된다.
  • list<char>를 선언한 후 입력 string의 값을 그대로 복사한다.
  • B 연산
    • list의 erase()
    • erase는 지우고 싶은 위치의 index를 전달하면 된다.
    • erase의 return 값은 지웠을 때의 pos 값이므로 cursor를 갱신한다.
  • P 연산
    • list의 insert()
    • 첫번째 인자는 삽입 위치, 두 번째 인자는 값이다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string s = "", ans = "";
	cin >> s;

	list<char> li(s.begin(), s.end());
	auto cursor = li.end();

	int M; cin >> M;
	while (M--) {
		char opt, c;
		cin >> opt;

		switch (opt)
		{
		case 'L':
			if (cursor != li.begin())
				cursor--;
			break;

		case 'D':
			if (cursor != li.end())
				cursor++;
			break;

		case 'B':
			if (cursor != li.begin())
				cursor = li.erase(--cursor);
			break;

		default:
			cin >> c;
			li.insert(cursor, c);
			break;
		}
	}

	for (auto cursor : li)
		cout << cursor;
}



5. 소감

  • 입력 크기 신경 안쓰고, string으로 해서 예제 돌아가길래
  • string insert, erase 썼다가 시간초과 받음..
  • 입력 크기 잘 보고 자료형 지정하자!