글 읽기 - 틀릴게 없는 것 같은데, 출력 초과가 뜨는 이유를 모르겠습니다.

applepie77 4년 전 1

나름 직관적으로 짠 코드이지만, 문제 될게 없어보이는데 말이죠.

#include<iostream>
#include <vector>
#include <string>
using namespace std;
string A, T;

int main(){
	cin >> A;
	cin >> T;
	int T_size = T.size();
	int A_size = A.size();
	int flag_1 = 0;
	int flag_2 = 0;
	
	int bg_start = 0;
	int ed_start = T_size - 1;

	while(true){
		flag_1 = 0;
		flag_2 = 0;
		for(int i =bg_start; i < T_size; i++){

			//맨 처음 발견된 A만을 삭제. 
			if(T.substr(i, A_size) == A){
				T.erase(i, A_size);
				T_size = T.size();
				(i - A_size) <= 0 ? bg_start = 0 : bg_start = i - A_size;
				flag_1 = 1;
				break;
			}
		}
	
		if(flag_1 == 0){break;}
	
		if(ed_start >= T_size){
			ed_start = T_size - 1;
		}
		
		for(int j = ed_start; j >=0; j--){		
		
			//맨 끝에 발견된 A만을 삭제. 
			if(T.substr(j, A_size) == A){
				T.erase(j, A_size);
				T_size = T.size();
				ed_start = j;
				flag_2 = 1;
				break;
			}
		}
		
		if(flag_2 == 0){break;}
	}
	
	cout<<T<<"\n";
	
	return 0;
}

pichulia 4년 전 4

이런 예제가 있을 수 있겠네요.

abcd

wrongabcabcabcdddanswer

어디서 문제가 되는지를 직접 확인해보시고...해당 코드를 정말 사소하게 고쳐서 맞을 수 있습니다.

applepie77 4년 전 0

와, 정말 간단한 오류가 있었네요, 생각하신 수정이 맞는지는 모르겠지만, bg_start 부분에서 탐색이 된 i 위치에서 그냥 A_size 만큼이 아니라, A_size 의 2배 만큼 앞으로 땡기면서 탐색하니깐 정답으로 나오네요. 10번가량 계속 오답으로 나와서 꼭 스택을 써야만 풀 수 있는 문제인가.. 라고 생각하고 거의 포기했는데 말이죠.

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

문제

문제

출처

ICPC

틀릴게 없는 것 같은데, 출력 초과가 뜨는 이유를 모르겠습니다.

applepie77 4년 전 1

pichulia 4년 전 4

applepie77 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말