글 읽기 - 문자열 폭발 어렵네요... 반례찾기 부탁드립니다 (설명있음)

phryxia 4년 전 0

COCI 홈페이지(https://hsin.hr/coci/archive/2013_2014/)에서 테스트 데이터를 다운받아서 검증하는데, 크기가 작은 예제는 맞았습니다.

그런데 크기가 큰 예제(구체적으로는 eksplozija.in.10a)에서 답이 엉뚱하게 나오네요.

FRULA가 나와야하는데 문자열이 덜터지고 이상한 문자열이 출력되었습니다.

크기가 너무 큰 탓에 손으로 검증할 방법이 없어서, 지푸라기라도 잡는 심정으로 여기에 글을 올리게 되었습니다.

로직은 주석으로 그려놨는데, 읽는데 불편함이 없기를 기도합니다 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;

int N, M;
char s[1000001];
char bomb[37];
stack <vector <int> > st_path; // 잠재적 폭발문자열들의 인덱스를 저장
stack <int> st_numb; // 폭발문자열의 진행정도를 저장 (1 ~ M)

int main(void)
{
	scanf("%s", s);
	scanf("%s", bomb);
	N = strlen(s);
	M = strlen(bomb);

	/*
		aabcbabcc
		abc

		aabcbabcc	numb	path
		^			1		[0]

		aabcbabcc	numb	path
		 ^			1,1		[0],[1]

		aabcbabcc	numb	path
		  ^			1,2		[0],[1,2]
		
		aabcbabcc	numb	path
		   ^		1,3		[0],[1,2,3]

		a___babcc	numb	path
		   ^		1		[0]

		a___babcc	numb	path
		    ^		2		[0,4]

		...
		
		a___b___c	numb	path
		        ^   3		[0,4,8]

		_________	numb	path
				^
	*/
	for (int i = 0; i < N; ++i)
	{
		if (s[i] == bomb[0])
		{
			st_numb.push(1);
			st_path.push(vector <int>());
			st_path.top().push_back(i);
		}
		else if (!st_numb.empty())
		{
			if (s[i] == bomb[st_numb.top()])
			{
				st_numb.top()++;
				st_path.top().push_back(i);
			}
			else
			{
				st_numb.pop();
				st_path.pop();
			}
		}
		if (!st_numb.empty() && st_numb.top() == M)
		{
			while (!st_path.top().empty())
			{
				s[st_path.top().back()] = '_';
				st_path.top().pop_back();
			}
			st_numb.pop();
			st_path.pop();
		}
	}

	bool frula = true;
	for (int i = 0; i < N; ++i)
	{
		if (s[i] != '_')
		{
			printf("%c", s[i]);
			frula = false;
		}
	}
	if (frula)
		printf("FRULA");
	return 0;
}

jintak0401 4년 전 4

반례 드릴게요.

01234567 --> 인덱스 보기 쉬우시라고 같이 올려요

abacabcc

abc

출력 : ac

옳은 답 : abacc

그리고 이 코드의 i 에 따른 st_numb 도 보여드립니다.

========== i : 0 =============
st_numb : 1
========== i : 1 =============
st_numb : 2
========== i : 2 =============
st_numb : 2 1
========== i : 3 =============
st_numb : 2
========== i : 4 =============
st_numb : 2 1
========== i : 5 =============
st_numb : 2 2
========== i : 6 =============
st_numb : 2 3
========== i : 7 =============
st_numb : 3

보시면 아시겠지만 중간에 2,3 인덱스의 ac 를 무시하고 ab__abcc 로 인식합니다. 그래서 ac 만 남네요

phryxia 4년 전 0

헉 감사합니다! 코딩에 뭔가 문제가 있었나봅니다. 좀 더 고민해보겠습니다 :)

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

문제

문제

출처

ICPC

문자열 폭발 어렵네요... 반례찾기 부탁드립니다 (설명있음)

phryxia 4년 전 0

jintak0401 4년 전 4

phryxia 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말