LeetCode[Java] - Longest Palindromic Substring 풀이

안녕하세요. Ruk 입니다. LeetCode의 Add Two Numbers Longest Palindromic Substring 문제를 풀어본 내용 공유하려 해요.

문제의 조건은 거꾸로해도 똑같으면서 가장 긴 문자열을 찾는 문제 입니다.

 

과거에 푼 적이 있는데 오랜만에 다시 풀어보았습니다.

네,,,,,, 약 100배나 속도가 더 걸리는 알고리즘을,,,,,,,,

같은 메모리를 사용하여 같은 결과물을 만들지만 속도차이가 이렇게 심하게 날 수도 있네요.

 

1030ms가 걸린 코드 입니다.

b(n^3)을 ㅎㅎㅎㅎ 당당하에 for문 중첩하여 돌렸고, checker에서도 1번 돌게되니 총 3번이 중첩된 최악의 코드 입니다.

퇴근하고 23시에 풀면 그럴수 있다고? 생각되네요 앜ㅋㅋㅋㅋㅋ

 

과거에 제가 어떻게 풀었는지 바로 확인해보니

과거와 현재 둘다 checker로 비교하는 로직은 같지만 중첩을 보시면 n^2의 시간복잡도로 문제를 해결하였내요.

 

문제에 대한 접근을 생각할 당시

1. 문자열을 잘라서 비교한다.

2. 앞뒤가 같은지 체크하여 최대길이를 저장한다.

 

위 2가지 로직을 고려하고 짠건 같지만 크게 다른점은 아래와 같습니다.

S 문자열을 subString 하기 위해서

i, j를 0~n까지 돌려가면서 길이를 측정하는 최악의 코드와

i를 0~n까지 돌려가며 해당 위치에서 좌우로 1칸씩 비교하는 코드

 

checker를 구현 시 조금만 더 생각했더라면 과거처럼 좋은 코드를 만들었을 건데 정말,,, 반성하게되는 코드네요.