글 읽기 - 제가 어느 부분에서 반례가 생기는지 전혀 모르겠습니다.

blue12342000 5년 전 0

제가 생각하고 그 생각대로 짠 소스 로직은 이렇습니다.

길이가 2 이상인 문자열이 들어올경우 그 문자가 대칭인지 확인합니다.
맞다면 그 길이를 리턴하고, 아니라면 가장 마지막 문자와 동일한 문자를 문자의 맨뒤 -1 인덱스부터 찾습니다.
찾은 해당 인덱스에서부터 마지막문자까지 대칭인지 확인합니다. ( 최악인경우 문자는 마지막 문자를 기준으로 대칭이 되기에 찾은 인덱스의 앞부분은 대칭으로 생각합니다.)
찾은 인덱스가 없거나 해당 인덱스에서 대칭이 아니라면 작업을 중단하고, 마지막 으로 대칭이였던 인덱스 번호 만큼 현재의 길이에 더해줍니다.

이게 제가 생각한것입니다.

fyhmh 7 xbmgwg 9 mdusys 9 gzpvp 7 mbdimpjrj 15 ebjftigbqb 17 xdnykkvk 13 tnmoiki 11 jzzxnxtaa 16 tozwz 7 iaytvrjbxzvv 22 xoovsimmomdytt 26 wknwaa 10 ngunouaxnmn 19 qwslufdioacjnclyl 31 jqemnn 10 dvqpp 8 opgoo 8 cnqbb 8 egxxx 7 zdxpx 7 jvtvv 8 xbuvumhm 13 wrsamzpp 14 rkitqt 9 ybqygy 9 zhmuvrvv 14 ezzpgwpvv 16 rayww 8 klokjj 10 wczxydeznn 18 ryibhgnajj 18 mhqeqpp 12 btrlddee 14 vsxkdkaa 14 mhkeczikumu 19 aqzhwzz 12 pozaa 8 xkgrlol 11 tudwfxses 15 thcpc 7 qrzxjrj 11 nzkuldllusu 19 asgmtbbbsgg 20 cqkkdywalsss 21 zgdivbff 14 oauiggzlzz 18 nljzj 7 gunncdd 12 cwztii 10 alyaca 9 haaotuu 12 zyiiuu 10 zzfbhb 9 bfomm 8 mmwdmixlx 15 bczyy 8 xxugagltatmyytt 28 qdjsj 7 azxsnln 11 sswvxzx 11 rthaa 8 azdbhqjxsx 17 dfpkoyqiszdigg 26 sbuhmss 12 yztqrbgg 14 odjvfqq 12 mtnsn 7 rpstet 9 rwzekdsbs 15 qjmjuj 9 shefe 7 tftzkjhcc 16 qbufsss 11 yxvzsvzpefrfsus 27 gpwuwu 9 catkaikzmlm 19 krlpgoivonff 22 btwoo 8 pdvmmm 9 yidhxdyiuiyd 17 rxkeek 8 lhpii 8

위는 제가 랜덤 문자열 생성으로 해서 반례를 찾으려 했었는데 랜덤으로 문자열 생성이라 그런지 반례가 되는 특정 문자열 생성이 너무 안나와서

이렇게 질문을 남깁니다.

혹여 문자열 길이가 0일때 1일때는 혹시 제가 잘못 생각한건가 싶어서 각각 (0, 1) (1, 1) (1, 2) (2, 2) 로도 변경을 해보았지만 아니였습니다.

물론 코드를 아예 처음부터 다른방식으로 짠다면 해당 문제는 정답으로 나올수도 있습니다만

저는 왜 이렇게 코딩한 결과는 어떤 원인으로 반례가 생기며, 어디를 내가 잘못 생각했는가를 알기위해서라도 현재의 상태에서의 반례를 알고 싶습니다.

#include <iostream>
#include <cstring>

using namespace std;

bool IsPalin(char* str, int s, int e)
{
	//s 부터 e까지 비교
	while (s < e)
	{
		if (str[s++] != str[e--])
		{
			return false;
			break;
		}
	}
	return true;
}

int main()
{
	// abcdba 11
	// aabc 7
	// sass 6
	// ssas 5
	// abcc 6
	// sascsc 9
	char str[1001];
	cin >> str;
	int strLen = strlen(str);
	int resLen ;
	if (strLen == 0) resLen = 0;
	else if (strLen == 1) resLen = strLen;
	else
	{
		bool isPalin = IsPalin(str, 0, strLen - 1);

		if (isPalin) resLen = strLen;
		else
		{
			resLen = strLen + strLen - 1;
			int idx = strLen - 1;
			char target = str[idx];
			while (idx > 0)
			{
				idx--;
				if (str[idx] == target)
				{
					if (IsPalin(str, idx, strLen - 1)) resLen = strLen + idx;
					else break;
				}
			}
		}
	}

	cout << resLen << endl;

	return 0;
}

seico75 5년 전 1

abkcbcbckb

메인에서 idx 를 증가방향으로 찾거나 break가 수정되어야 할꺼 같네요

blue12342000 5년 전 0

정말 감사드립니다. 덕분에 해결했습니다.

제가 대칭 문자열 찾는것을 마지막 문자열을 기준으로 한것이 문제 였었네요.

길이가 2 이상인 문자열이 들어올경우 그 문자가 대칭인지 확인합니다.
맞다면 그 길이를 리턴하고, 아니라면 가장 마지막 문자와 동일한 문자를 ~~문자의 맨뒤 -1 인덱스부터 찾습니다~~ 문자의 시작 인덱스부터 확인
찾은 해당 인덱스에서부터 마지막문자까지 대칭인지 확인합니다. ( 최악인경우 문자는 마지막 문자를 기준으로 대칭이 되기에 찾은 인덱스의 앞부분은 대칭으로 생각합니다.)
찾은 인덱스가 없거나 해당 인덱스에서 대칭이 ~~아니라면~~ 대칭이면 작업을 중단하고, 마지막 으로 대칭이였던 인덱스 번호 만큼 현재의 길이에 더해줍니다.

정말 감사드립니다. 왜 저부분이 틀렸을거라고는 생각을 못한건지 아쉽네요.

가장 짧은 대칭 문자열을 만드는것이기에 최대길이의 대칭부터 확인하는식으로 했어야 했는데, 반대로 생각해서 이런 문제가 나온거 같네요

도움에 정말 감사드려요

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

문제

문제

출처

ICPC

제가 어느 부분에서 반례가 생기는지 전혀 모르겠습니다.

blue12342000 5년 전 0

seico75 5년 전 1

blue12342000 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말