[일반] 이거 어떻게 풀어요

[ㅁㄴㅇㄴㅁ(222.97)]

프로그래머스에 있는 팰린드롬문젠데,

dp문제인가...더이상 코드를 못짜겠어요 헬프,,.

[닐스보어(uzicha12)]

2중 for문 쓰면 될거 같은데 'ㅅ' 문자열 s[0] 부터 s[-1] 까지 구해서 문자열 s[0]으로 시작되는 팰린드롬 최대 크기를 구하고(팰린드롬이 아니게 될 경우에는 break; 이걸 다시 문자열 s[1]부터 s[-1] 까지 구하는 식으로요. 물론 이런식으로 하면 성능이 그다지 좋을거 같지는 않고 굇굇들은 더 좋은 방법이 있겠지만 문자열 최대 길이가 2500이니 뭐.

[익명(125.132)]

DP로 풀었어요.

[익명(223.62)]

O(n) hashing or manacher's algo., O(n^2) d[s][e] = true if str[s:e] is palindrome

[0xrgb(0xrgb)]

해싱이 왜 n이야 n lg n 이지