글 읽기 - 반례 간절하게 고대합니다..

huh0918 1년 전 0

예제 다 맞고 논리적으로 그대로 구현했는데 어디가 문제일까요 .. 도움 주시면 정말 감사하겠습니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

struct STACK{
	int arr[300000];
	int top;
	int size;
	
	STACK(int _top = -1, int _size =0) : top(_top), size(_size) {} 
	void push(int idx) {
		arr[++top] = idx;
		size++;
	}
	int pop() {
		size--;
		return arr[top--];
	}	
};
// 찾았으면 삭제처리하고 true, 못찾으면 false
bool check(STACK &s, vector<bool> &is_deleted, const string &text, const string &target) {
	
	int len = target.size();
	
	if (s.size < len   ) // stack이 target보다 짧으면 볼 필요 없음
		return false;

	int s_idx = s.size - len;
	for (int i=0; i <len; ++i) {
	 	if ( target[i] != text[ s.arr[s_idx+i] ] )
			return false;
	}
	
	for (int i=0; i <len; ++i) {
	 	int idx = s.pop();
		is_deleted[idx] = true;
	}
	
	return true;
}

int main() {
	cin.tie(nullptr); ios_base::sync_with_stdio(false);
	string a, t;
	cin >> a >> t;
	string b(a.rbegin(), a.rend());
	vector<bool> is_deleted(t.size(), false);
	
	STACK fs, bs;
	int left=0, right = t.size()-1;
	while ( true )
	{
		bool del_complete;
		
        //  left -> 
		del_complete = false;
		while (left < t.size()) {
			
			if (is_deleted[left]) {
				left++;
				continue;
			}
			
			fs.push(left++);
			if ( check(fs, is_deleted, t, a) ) { // 있으면 지우고  true, 없으면 false
				del_complete = true;
				break;
			}
		}
		if (!del_complete)
			break;
		
        //  <- right
		del_complete = false;
		while(right>=0) {
			
			if (is_deleted[right]) {
				right--;
				continue;
			}
			
			bs.push(right--);
			if ( check(bs, is_deleted, t, b) ) { // 있으면 지우고  true, 없으면 false
				del_complete = true;
				break;
			}
		}
		if (!del_complete)
			break;
	
	} // big while

	for (int i=0; i<t.size(); ++i)
		if ( !is_deleted[i] )
			cout << t[i];
	cout << endl;
}

pmn0001 1년 전 0

몇번 문제인가요?

huh0918 1년 전 0

앗 수정했습니다

tjdgnsqn3 1년 전 1

abc
abcababababababcababccccc

answer
abab

huh0918 1년 전 1

덕분에 문제점 알았습니다. 이미 스택에 들어가있는데 반대쪽에서 오면서 삭제해버리면 중복으로 삭제처리가 되네요 감사합니다!

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

문제

문제

출처

ICPC

반례 간절하게 고대합니다..

huh0918 1년 전 0

pmn0001 1년 전 0

huh0918 1년 전 0

tjdgnsqn3 1년 전 1

huh0918 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말