dokrsky   7달 전

입력으로 주어진 abab를 봤을 때, 제가 생각한 알고리즘은 이겁니다.

a[0] = a

a[1] = b

a[2] = a

a[3] = b     니까

a[0] == a[3] 이면 

left++, right--이고, 만약 위의 조건이 틀리다면 오른쪽에 어떤 문자가 추가되었다고 가정하고, left++만 했습니다.

이런 식으로 left++만 했을 때, cnt를 세어주고 결과 값으론 기본문자열 길이 + cnt 를 출력해주었습니다.

몇 가지의 추가 케이스를 넣어봤는데도 이상없이 동작했는데, 제가 놓치는 반례 혹은 부분이 있을까요??

nsy0042   7달 전

전 이문제 안풀어봤지만, 제가 몇가지 해본 것 중에

PERMITE라는 7자리 수 입니다.

이것을 넣었을 경우 11이라는 숫자가 나오며, 실제 정답은 13이 나와야 합니다.

dokrsky   7달 전

nsy0042 님 감사합니다. 그런 반례를 생각못했었네요!!

zagame   7달 전

저도 이렇게만 생각했는데 반례가 많은거 같더라구요..... 하 막힘 ㅠㅠ

atomzeno   7달 전

모든 i번째 문자를 중심으로 잡고 팰린드롬을 만들어가면 1000*2001시간복잡도로 될듯?

zagame   7달 전

맨 왼쪽과 맨 오른쪽을 제외한 i번째 문자 말씀이신가요?

atomzeno   7달 전

정확히는 (n+1)/2~n번째 문자까지 각각이 중심이 되어 팰린드롬이 될수 있는지 확인해보면 될듯합니다.

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