[ 백준 / 1406 ] 에디터 (C++)

https://www.acmicpc.net/problem/1406

 

난이도 : 실버 2 
알고리즘 유형 : 자료구조, 덱  
풀이 시간 : 17분 

문제 풀이 

에디터를 구현하려고 한다. 에디터에는 커서가 존재하는데, 각 명령어에 따라 문장을 수정할 수 있다. 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하자.

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

 

문제를 읽고 바로 생각날 수 있는 알고리즘은 단순한 구현이다. 커서를 인덱스로 지정해둔 뒤, 각 명령어가 입력될 때 마다 삽입 삭제를 반복해주면 된다. 하지만 이 방법을 사용할 시, 리스트 내부에서 인덱스 삽입 삭제 과정에 $O(n)$의 시간복잡도가 소요되기 때문에 최적화를 하지 못하게 된다.

 

따라서 `deque` 자료구조를 사용해서 양 끝 부분만 비교를 해 줄 것이다. `deque`의 경우, front 혹은 back 부분에 한해 삽입 삭제 시 $O(1)$의 시간복잡도가 걸리기 때문에 효율적으로 사용할 수 있다.

 

문제에 필요한 덱은 총 2개이다. 하나는 커서의 이전 문자들을 저장하는 인덱스, 다른 하나는 커서 이후 문자들을 저장할 것이다.

이제 명령어에 맞춰 명령을 수행하면 된다.

만약 'L' 명령어라면, 커서를 왼쪽으로 이동해야 하기 때문에 왼쪽 덱의 끝 문자를 pop 한 뒤, 오른쪽 덱의 front에 넣어준다.

만약 'D' 명령어라면, 커서를 오른쪽으로 이동해야 하기 때문에 오른쪽 덱의 front 문자를 pop 한 뒤, 왼쪽 덱의 back에 넣어준다.

'B' 명령어라면 문자를 삭제하는 것이기 때문에 단순히 왼쪽 덱의 back 문자를 pop해준다.

'P' 문자는 새로운 문자를 커서 왼쪽에 추가하는 것이기 때문에, 왼쪽 덱의 back에 push 해준다.

 

이후, 왼쪽 덱과 오른쪽 덱을 순차 탐색하며 완성된 문자열을 출력하면 된다.

 

시간복잡도는 명령어의 개수인 $O(m)$만큼 소요된다.

 

코드

/*
커서가 위치할 수 있는 곳  : L + 1
L : 왼쪽
D : 오른쪽
B : 커서 왼쪽 문자를 삭제(문장의 맨 앞이라면 무시)
P : $라는 문자를 커서 왼쪽에 추가
커서는 문장의 맨 뒤에 위치하고 있음

풀이 : 중간에 insert 하는게 더 시간 오래걸림 
댁 사용하기 : L이라면 push, D라면 pop, B면 그냥 삭제, P는 추가
*/

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int n, m;
string s;

int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> s >> m;
	n = s.size();

	deque<char> stackIn;
	deque<char> stackOut;
	for (int i = 0; i < n; i++)
		stackIn.push_back(s[i]);

	char order;
	char c;
	while (m--) {
		cin >> order;
		if (order == 'P') {
			cin >> c;
			stackIn.push_back(c);
		}
		else if (order == 'L') {
			if (stackIn.empty())
				continue;
			stackOut.push_front(stackIn.back());
			stackIn.pop_back();
		}
		else if (order == 'D') {
			if (stackOut.empty())
				continue;
			stackIn.push_back(stackOut.front());
			stackOut.pop_front();
		}
		else {
			if (stackIn.empty())
				continue;
			stackIn.pop_back();
		}
	}

	for (auto s : stackIn)
		cout << s;
	for (auto s : stackOut)
		cout << s;

	return 0;
}

배운 점 

자료구조를 활용하여 간단하게 해결할 수 있는 문제였다.

하지만 자료구조는 생각보다 광범위한 곳에서 활용되기 때문에 꾸준히 공부해두면 좋을 것 같다.