백준) 5397 키로거 (스택)

키로거

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

입력 케이스는 캐릭터와 좌우 화살표, 백스페이스로 분류된다.

캐릭터를 제외한 추가 키 들에 대한 기능을 정의해야 하는데,

좌우 화살표의 입력은 문자열 자체를 변경하진 않고 캐릭터가 입력될 위치(커서)를 바꾼다.

백스페이스는 현재 커서 바로 앞의 캐릭터를 지워야 한다.

위와 같은 기능을 구현하기 위해,

커서의 앞뒤를 구분하면서, 부가 키의 입력 시에 빠른 결과를 리턴해줄 구조를 짜야 하는데,

이를 스택으로 구현한다면 선형시간에 모든 기능이 수행된다.

커서의 앞과 뒤를 두 개의 스택으로 생각한다면

캐릭터의 입력은 앞의 스택에 push,

왼쪽 화살표는 앞 스택에서 pop -> 뒤 스택에 push,

반대로 오른쪽 화살표는 뒤 스택에서 pop -> 앞 스택에 push,

백스페이스는 앞 스택에서 pop

으로 구현할 수 있다.

기타 예외처리를 추가한 코드는 다음과 같다.

#include <stdio.h>
 
int T;
char buf[1000001];
int len;
int strlen(char buf[]) {
    int cnt = 0;
    while (buf[cnt] != '\0')
        cnt++;
    return cnt;
}
 
char stack1[1000001];
char stack2[1000001];
int stack1_size;
int stack2_size;
 
void stack_push(char stack[], char c, int& size) {
    stack[size++] = c;
}
char stack_pop(char stack[], int& size) {
    return stack[--size];
}
 
int main() {
    scanf("%d", &T);
 
    while (T--) {
        scanf("%s", buf);
        len = strlen(buf);
 
        for (int i = 0; i < len; ++i) {
            if (buf[i] == '<') {
                if (stack1_size == 0)
                    continue;
 
                stack_push(stack2, stack_pop(stack1, stack1_size), stack2_size);
            }
            else if (buf[i] == '>') {
                if (stack2_size == 0)
                    continue;
 
                stack_push(stack1, stack_pop(stack2, stack2_size), stack1_size);
            }
            else if (buf[i] == '-') {
                if (stack1_size == 0)
                    continue;
 
                stack_pop(stack1, stack1_size);
            }
            else
                stack_push(stack1, buf[i], stack1_size);
        }
 
        for (int i = 0; i < stack1_size; ++i)
            printf("%c", stack1[i]);
        for (int i = stack2_size-1; i >= 0; --i)
            printf("%c", stack2[i]);
        putchar('\n');
 
        stack1_size = 0;
        stack2_size = 0;
    }
 
    return 0;
}