BOJ 1406 : 에디터

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1406

 

참고 

- BOJ 5397 : 키로거

 

 

stack을 2개 이용하면 에디터의 문자열을 쉽게 관리할 수 있다.

 

먼저 초반에 abcd가 입력되었다고 하자. 커서는 바로 d의 옆에 존재한다. (sp1 = 4)

→ abcd|

 

이제 P e 명령어에 의해 e가 추가되었다고 하자.

stack1의 크기를 늘려주면서 e를 넣어주면 된다. (sp1 = 5)

stack1[sp1++] = 'e';

→ abcde|

 

이제 L 명령어에 의해 왼쪽으로 옮긴다고 하자.

왼쪽으로 옮기는 것은, 문자열은 여전히 abcde 이지만 커서는 d 뒤에 위치하게 된다.

따라서 커서의 뒷부분을 stack2로 옮겨준다. (sp1 = 4, sp2 = 1)

stack에서 가장 나중에 들어온 값은 stack[sp - 1]이므로,

 

stack2[sp2++] = stack1[sp1-- - 1];

→ abcd|e

 

stack1[4]에는 여전히 e가 남아있지만, 상관없다.

왜냐하면 sp1이 4이기 때문에, (0 ~ 3까지만)stack1에서 유효한 문자는 abcd라는 것을 알 수 있다.

 

다시 L 명령어에 의해 커서를 왼쪽으로 옮겨보자. sp2는 증가하고, sp1은 감소할 것이다. (sp1 = 3, sp2 = 2)

stack2[sp2++] = stack1[sp1-- - 1];

→ abc|de

마찬가지로, d가 stack1에 남아있는 것은 상관없다. sp1으로 abc까지만 유효한 것을 알 수 있게 해준다.

또한 stack의 특성(후입선출)에 의해, stack2는 문자열이 거꾸로 쌓인다. 

하지만 stack2는 거꾸로 출력하면 문자열이 원래 순서대로 복구되므로 현재의 문자열을 알 수 있다.

 

stack1은 start = 0 ~ start < sp1 까지 출력하고,

stack2는 start = sp2 - 1 ~ start >= 0이 될 때까지 출력하면

abcde가 출력된다.

 

이제 D 명령어에 의해, 오른쪽으로 커서를 옮겨보자. sp1이 증가하고, sp2가 감소한다. (sp1 = 4, sp2 = 1)

stack1[sp1++] = stack2[sp2-- - 1];

→ abcd|e

커서만 옮겼으므로, stack의 크기는 변하였지만 여전히 abcde가 출력된다는 것을 확인해보자.

 

이제 B 명령어를 이용해 왼쪽 커서를 이동하면서 문자열 하나를 지우자. 이것은 sp1만 감소시킨다. (sp1 = 3)

sp1--;

→ abc|e

stack1의 sp1의 크기만 변경되었다.

위에 설명한 것처럼 출력을 시도하면 abce가 되는 것을 알 수 있다. sp1이 3이기 때문이다.

 

마지막으로, P f 명령어로 문자열을 추가해보자. (sp1 = 4)

stack1[sp1++] = 'f';

→ abcf|e

출력하면 abcfe가 됨을 알 수 있다.

 

정리하면 다음과 같다.

L 명령어	stack1의 값을 stack2에 추가, sp1을 감소시키면서 sp2를 추가
D 명령어	stack2의 값을 stack1에 추가, sp2를 감소시키면서 sp1을 추가
B 명령어	sp1을 감소
P $ 명령어	sp1을 증가시키며 $ 입력

 

실제로는 stack이 비어있는 경우 예외처리를 해줘야 한다.

커서가 가장 왼쪽이나 오른쪽일 경우 명령을 무시하기 때문이다.

stack이 비어있는지는 if(sp)로 판단이 가능하다.

 

최종 코드는 아래를 참고하자.

최초의 input에서 문자열의 길이를 구하는 함수가 필요하므로 strlen 함수는 아래에서 편한 것을 쓰자.

int mystrlen(char * str) 
{
	int len = 0;

	while (*str++) len++;
	
	return len;
}

int mystrlen2(char * str)
{
	int len = 0;

	while (str[len++]);

	return len - 1;
}

 

#include <stdio.h>

int N;

char stack1[600100];
char stack2[600100];
int sp1, sp2;

int mystrlen(char * str) 
{
	int len = 0;

	while (*str++) len++;
	
	return len;
}

int mystrlen2(char * str)
{
	int len = 0;

	while (str[len++]);

	return len - 1;
}

int main(void)
{
	char ch, tmp;

	scanf("%s", stack1);

	sp1 = mystrlen(stack1);

	scanf("%d", &N);
	for (int i = 0; i < N;i++)
	{
		scanf(" %c", &ch);

		if (ch == 'L')
		{
			if(sp1) stack2[sp2++] = stack1[sp1-- - 1];
		}
		else if (ch == 'D')
		{
			if(sp2) stack1[sp1++] = stack2[sp2-- - 1];
		}
		else if (ch == 'B')
		{
			if(sp1) sp1--;
		}
		else
		{
			scanf(" %c", &tmp);
			stack1[sp1++] = tmp;
		}
	}

	for (int i = 0; i < sp1; i++) printf("%c", stack1[i]);
	for (int i = sp2 - 1;i >= 0; i--) printf("%c", stack2[i]);

	putchar('\n');

	return 0;
}