C++) 백준 1406번 풀이_에디터

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

1406번: 에디터

연속 배열 처리에는 Linked list 처리가 좋다 라는 것과

getchar 및 scanf를 사용한 입력 받아들이기에 있어서

버퍼 처리에 대한 공부를 착실하게 한 문제ㅠ ㅠ ㅠ ㅠ ㅠ....

 

scanf나 getchar로 캐릭터를 하나씩 받아올 경우, 개행문자가 버퍼에 남아있기 때문에

개행문자를 버퍼에서 빼주는 처리가 꼭꼭 필요하다.

 

첨엔 그냥 최대길이 600000개의 캐릭터 배열을 만들어서 커서를 이동하려고 했는데,

그렇게 하니까 중간삽입과 중간삭제에서 해야하는 복사가 시간을 겁나게 잡아먹는 것이다.;

 

결국 시간초과 떠서 해당 코드는 폐기.

 

#include<iostream>
#include<string>
#include<list>
using namespace std;

int main() {
	string editor, clipboard;
	int cursor, comcnt;
	char command, addinp;
	cin >> editor;

	cursor = editor.length(); 
	cin >> comcnt;

	for (int i = 0; i < comcnt; ++i)
	{
		cin >> command;
		if ('L' == command)
		{
			if( cursor > 0 )
				cursor -= 1;
		}
		else if ('D' == command)
		{
			if (cursor < editor.length())
				cursor += 1;
		}
		else if ('B' == command)
		{
			if (cursor > 0)
			{
				clipboard = editor.substr(cursor, editor.length());
				editor.erase(cursor - 1, editor.length());
				editor += clipboard;
				clipboard.clear();
				cursor -= 1;
			}
		}
		else if ('P' == command)
		{
			cin >> addinp;
			bool input = false;
			if (cursor != editor.length())
			{
				input = true;
			}

			if (input)
			{
				clipboard = editor.substr(cursor, editor.length());
				editor.erase(cursor, editor.length());
			}
			editor += addinp;

			if (input)
			{
				editor += clipboard;
				clipboard.clear();
			}

			cursor += 1;
		}
	}

	cout << editor;
}

 

 

그래서 문제에 붙은 태그를 확인해보니 '연결 리스트'라고 되어있어서

Double linked list가 구현되어있는 List container를 사용해서 문제를 풀었다....

 

여태 백준에서 문제풀 때 언어를 C++로 놔두고 풀어서

auto가 사용이 불가능하다는 것을 이제야 깨달았다...

iterator를 사용하여 코드를 수정해서 제출했다.

 

 

메모리랑 시간을 겁나 많이 잡아먹지만 일단 푸는데 성공.

#include<stdio.h>
#include<string>
#include<list>
using namespace std;

int main() {
	char input1, input2;

	list<char> editor;

	char input;

	input = getchar();

	while ('a'<= input && input <= 'z' )
	{
		editor.push_back(input);
		input = getchar() ;
	}
	list<char>::iterator cursor = editor.end();

	int comcnt;
	scanf("%d", &comcnt);
	getchar();

	for (int i = 0; i < comcnt; ++i)
	{
		char command ;
		scanf("%c", &command);
		getchar();

		if ('L' == command)
		{
			if( 0 != editor.size() && 
				cursor != editor.begin() )
				cursor--;
		}
		else if ('D' == command)
		{
			if( cursor != editor.end())
				cursor++;
		}
		else if ('B' == command)
		{
			if (0 != editor.size() &&
				cursor != editor.begin())
			{
				cursor--;
				cursor = editor.erase(cursor);
			}

		}
		else if ('P' == command)
		{
			scanf("%c", &input);
			getchar();
			cursor = editor.insert(cursor, input);
			cursor++;
		}
	}

	for (list<char>::iterator it = editor.begin(); it != editor.end(); it++)
	{
		printf("%c", *it );
	}
}

 

* 연결리스트 구현이 처음이라 참고를 많이 함

- https://blockdmask.tistory.com/76