글 읽기 - 1406) c언어 스택으로는 시간초과 해결이 불가능한가요?

swjo0502 1년 전 0

안녕하세요. c언어 스택구현으로 풀어봤습니다.

이 중, push와 pop 함수에서 스택 배열 중 커서의 위치에 따라 모든 배열 원소를 뒤로 1칸씩 밀거나, 앞으로 1칸씩 당겨오면서 시간초과가 발생함은 알았습니다.

근데 이런 방법 말고도 c언어로 해결할 방법이 있을까요...? 많이 고민해봐도 생각이 전혀 나지 않아 질문드립니다ㅜㅜ

#include <stdio.h>
#include <string.h>

char stack[600001];
int top = -1, cursor = -1;

void push(char operand, int index) {
	top++;
	if (top != cursor) {
		for (int i = top - 1; i >= cursor;i--) {
			stack[i + 1] = stack[i];
		}
	}
	cursor++;
	stack[cursor - 1] = operand;
}

void pop(int index) {
	for (int i = index + 1; i <= top;i++) {
		stack[index] = stack[i];
	}
	top--;
}

int main() {
	int n;
	scanf("%s", stack);
	top = strlen(stack) - 1;
	cursor = top + 1;
	scanf("%d", &n);
	for(int i = 0 ; i< n ; i++){
		char oper, operand;
		scanf(" %c", &oper);
		if (oper == 'L') {
			if (cursor == 0) continue;
			cursor--;
		}
		else if (oper == 'D') {
			if (cursor == top + 1) continue;
			cursor++;
		}
		else if (oper == 'B') {
			if (cursor == 0) continue;
			pop(--cursor);
		}
		else if (oper == 'P') {
			scanf(" %c", &operand);
			push(operand, cursor);
		}
	}
	for (int i = 0; i <= top;i++) {
		printf("%c", stack[i]);
	}
}

irsam78 1년 전 2

커서를 기준으로 앞에 있는 문자열과 뒤에 있는 문자열을 따로 스택을 관리하면 가능할것 같습니다.

https://www.acmicpc.net/proble...

비슷한 문제입니다. 해당 아이디어로 위 문제를 구현한 코드도 같이 첨부합니다.

도움이 되길 바랍니다. 화이팅

#include<stdio.h>

#define MAX_LEN 1000000
#define MARGIN 1

typedef struct{
    char stack[MAX_LEN+MARGIN];
    int top;
}Stack;

int main(){
    int T;
    Stack frontOfCursor, rearOfCursor;

    scanf("%d", &T);    getchar();
    while(T-- > 0){
        frontOfCursor.top = -1;
        rearOfCursor.top = -1;

        char c;
        while((c = getchar()) != '\n'){
            switch(c){
                case '<':
                    if(frontOfCursor.top >= 0)
                        rearOfCursor.stack[++rearOfCursor.top] = \
                        frontOfCursor.stack[frontOfCursor.top--];
                    break;
                case '>':
                    if(rearOfCursor.top >= 0)
                        frontOfCursor.stack[++frontOfCursor.top] = \
                        rearOfCursor.stack[rearOfCursor.top--];
                    break;
                case '-':
                    if(frontOfCursor.top >= 0)
                        frontOfCursor.top--;
                    break;
                default:
                    frontOfCursor.stack[++frontOfCursor.top] = c;
            }
        }
        
        for(int i = 0;i <= frontOfCursor.top;i++){
            printf("%c", frontOfCursor.stack[i]);
        }
        while(rearOfCursor.top >= 0){
            printf("%c", rearOfCursor.stack[rearOfCursor.top--]);
        }
        puts("");
    }

    return 0;
}

swjo0502 1년 전 0

@irsam78

스택을 2개 이용하면 되는군요

감사합니다 많은 도움이 되었습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1406) c언어 스택으로는 시간초과 해결이 불가능한가요?

swjo0502 1년 전 0

irsam78 1년 전 2

swjo0502 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말