반응형
가장 긴 팰린드롬
-
프로그래머스 Lv.3) 가장 긴 팰린드롬알고리즘/프로그래머스 2020. 5. 27. 22:42
가장 긴 팰린드롬 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 풀이 세 가지 풀이를 시도한 문제다. 첫번째로 시도한 방법은 이분 탐색이었다. binary search로 답이 충분히 나올 수 있다고 생각했지만, 답이 홀수개라면 mid가 답보다 작은 짝수가 됐을 때 팰린드롬이 형성되지 않아서 답까지 mid가 커지지 못하는 경우가 있었다. (홀 짝 반대의 경우도) 그래서 여러가지를 고려하다가 결국 실패했고, 완전탐색을 하고자 마음먹었다. 두번째로 시도한 방법..