[BAEKJOON] 1406_에디터_C언어

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

풀이

처음에 단순히 배열을 사용하여 풀고자 하였습니다. Point라는 변수를 커서 역할로하여 L이면 Point를 왼쪽으로, D면 오른쪽으로, B면 삭제하고 0을 대입하여 출력시 0이면 뛰어 넘도록 하였습니다. 그리고 P를 입력 받으면 입력되야되는 부분 뒤로 배열을 전부 한 칸씩 이동시켰습니다.

위는 처음 생각한 풀이에서 P를 수행할 때 x가 입력되야되는 지점 뒤로 다 뒤로 한 칸씩 미루고 대입을 하였습니다. 이 경우 명령에 대한 수행과 배열을 미루는 수행으로 인해 시간 복잡도가 n^2이 되어 시간초과가 나더군요.

그래서 2개의 배열로 스택 2개를 만들어서 문제를 풀었습니다.

처음 ABCDE를 입력 받은 후 순서대로 L, D, B, P x를 수행한 모습을 나타내었습니다. 작은 파란 화살표은 L-stack의 Top을 작은 노란 화살표는 R_stack의 Top을 의미합니다.

L은 L_stack의 Top 위치의 문자를 R_stack으로

D는 R_stack의 Top 위치의 문자를 L_stack으로

B는 L_stack의 Top 위치의 문자를 삭제

P는 L_stack의 Top+=1을 하여 x를 대입합니다.

출력은 L_stack의 0부터 L_stack의 Top까지 출력 후 R_stack의 Top부터 0까지 출력하면 됩니다.

P의 경우 문자를 대입해야 하므로 문자를 저장하기 위하여 char direction[500000][2];의 이차원 배열을 사용하였으나, char direction[500000][2];의 배열을 사용하지 않고 바로 명령을 수행하는 반복문 안에서 바로바로 명령을 입력받고 수행하는 것이 효율적일 것 입니다.

#include <stdio.h>

//L 커서 왼쪽으로, D 오른쪽으로, B 왼쪽 삭제, 왼쪽에 커서 추가.

void input();

void function();

void output();

char Left_stack[100001],Right_stack[100001];

char direction[500000][2];

int Left_top = -1, Right_top = -1,N,length;

int main()

{

input();

function();

output();

return 0;

}

void input()

{

Left_top=length=strlen(gets(Left_stack));

Left_top--;

scanf("%d", &N);

getchar();

for (int i = 0; i < N; i++)

{

scanf("%c", &direction[i][0]);

if (direction[i][0] == 80)

{

getchar();

scanf("%c", &direction[i][1]);

}

getchar();

}

}

void function()

{

for (int i = 0; i < N; i++)

{

switch (direction[i][0])

{

case 76://L

if (Left_top == -1) break;

Right_stack[++Right_top] = Left_stack[Left_top--];

break;

case 68://D

if (Right_top == -1)break;

Left_stack[++Left_top] = Right_stack[Right_top--];

break;

case 66://B

if (Left_top == -1)break;

Left_stack[Left_top--] = 0;

length--;

break;

case 80://P

Left_stack[++Left_top] = direction[i][1];

length++;

break;

}

}

}

void output()

{

for (int i = 0; i <= Left_top; i++)

printf("%c", Left_stack[i]);

for (int i = Right_top; i >= 0; i--)

printf("%c",Right_stack[i]);

printf("\n");

}