백준 1406 에디터

에디터 (백준 1406)

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

문제의 시간 제한과 메모리 제한에서 일부 힌트를 얻은 문제이다
일단 문제에서 0.3초의 시간제한을 주었으며, 대입되는 데이터의 수가
상당히 많아보였기에, 일반적인 string 의 insert 등을 사용하는 경우
시간초과가 확실해 보였기에 해당 방식은 시도하지 않았다

처음에는 deque 하나와 ‘index’라는 정수형 변수로 문제를 풀려다
결국 시작하는 ‘문자’에 대한 처리를 따로 해줘야 할지 고민하다
다시 ‘메모리 제한’을 보니 512mb 정도 되었기에
deque를 하나 더 사용하고,
그걸 기준으로 ‘커서’를 표현하면 될 것 같아
해당 방식으로 문제를 해결하였다

자료구조에 대한 이해를 묻는 문제였으며,
단순히 deque를 2개 사용했을 뿐인데
문제가 생각보다 쉽게 풀렸기에 자료구조 역시
알고리즘 만큼 중요한 요소인 점을 다시 알 수 있었다

Code

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

using namespace std;

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

	deque<char> queL,queR;
	string str;
	int iCount;
	cin >> str >> iCount;

	for (char c : str)
	{
		queL.push_back(c);
	}

	// 커서를 기준으로 queL과 queR을 이용
	// 시간 제한이 빡빡하지만
	// 메모리 제한은 다소 널널하므로
	// deque 2개 사용
	// 왼쪽 큐(커서 왼쪽)
	// 오른쪽 큐(커서 오른쪽)
	// 기본적으로 P 입력 시 오른쪽 큐에 push_front
	// B 입력 시 왼쪽 큐에서 pop_back\
	// L입력 시 queL의 뒤를 하나 빼서 오른쪽 큐에 push_front
	// R입력 시 queR의 앞을 하나 빼서 왼쪽 큐에 push_back
	// 출력시 queL부터 출력 후, queR 출력
	const char ind[] = {'L','D','B','P'};
	for (int i = 0; i < iCount; i++)
	{
		char temp;
		cin >> temp;
		switch (temp)
		{
		case 'L':
		{
			if (queL.size() == 0)
			{
				break;
			}

			char t = queL.back();
			queL.pop_back();
			queR.push_front(t);
		}
		break;

		case 'D':
		{
			if (queR.size() == 0)
			{
				break;
			}

			char t = queR.front();
			queR.pop_front();
			queL.push_back(t);
		}
		break;

		case 'B':
		{
			if (queL.size() == 0)
			{
				break;
			}

			queL.pop_back();
		}
		break;

		case 'P':
		{
			char addC;
			cin >> addC;

			queL.push_back(addC);
		}
		break;
		default:
			break;
		}
	}

	for (auto l : queL)
	{
		cout << l;
	}

	for (auto r : queR)
	{
		cout << r;
	}

	return 0;
}

해결 아이디어

1. 시간 제한이 매우 짧되, 메모리 제한이 512mb로 다소 널널하다
   여기서 일반적인 문자열 삽입 방식을 사용하는 경우는
   시간 초과가 날것이라 생각하고 원형 큐 혹은 deque 등의 자료구조를 생각해보았다
   
2. ‘커서’를 기준으로 왼쪽과 오른쪽 큐를 나누었다
   (deque 방식을 사용)
   
3. 각각의 명령어에 따라서 ‘커서’의 위치가 바뀔 때,
   커서의 왼쪽에 해당한다면 queL에,
   오른쪽이라면 queR에 요소를 집어넣었다
   
4. 출력시, 왼쪽 큐부터 차례대로 문자를 출력한다