[Programmers] 가장 긴 팰린드롬 - kotlin

가장 긴 팰린드롬 (Level3)

link - https://programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

 

1. 문제 파악하기

팰린드롬 - 앞뒤로 뒤집어도 똑같은 문자열을 말한다 

ex) abcba / abccba 

 

문자열이 주어졌을때 가장긴 팰린드롬 길이를 구한다 

 

- 입력 : 문자열 (ex. eabcbai)

- 출력 : 문자열에서 가장 긴 팰린드롬 길이를 구한다 (ex. 5)

 

2. 아이디어

- 먼저 팰린드롬인지 판단할 수 있는 함수 checkP를 생성한다.

- checkP :  문자열의 시작점, 끝점을 받아서 각각 비교해나가며 문자를 검사한다. 틀린경우 바로 return false하여 시간을 줄인다 

- 이제 주어진 문자열에서 시작점과 끝점을 바꿔가며 checkP를 불러주면 된다 

- 우선 문자열이 가장 긴 경우부터 길이를 줄여가며 검사하며, 팰린드롬이 되는 경우를 포착한경우 바로 정답을 반환할수있도록 한다 (가장 작은 경우부터 == 문자가 1개거나 2개인경우 부터 검사하면 모든 경우를 다 돌아야하기떄문에 시간적 비효율이 발생)

- 2차 for 문을 돌것인데 밖에 for문은 시도해보려고하는 문자열의 길이에 해당하는 for문이다 : 최초 주어진 문자열 s의 길이부터 시작해서 하나씩 줄여갈것이다

- 안에 for문은 시작점과 끝점을 선정하는 for문이다 

 

도식화하여 예를 들면

시도해보려고 하는 문자열 길이 (첫번째 for문 len) : 4
주어진 문자열  eabcbai 

두번째 for문을 도는 과정

e  a  b  c  b  a  i
s          e
    s          e
         s         e
             s         e

위와 같은 과정으로 eabc / abcb / bcba / cbai 이렇게 네개의 문자열을 검사하는 것!!! 사실 위의 과정은 예를들기위한 경우이고 이미 len이 5인경우 abcba에서 팰린드롬을 찾아 정답을 반환했을것이다~~

코드로 구현하면 아래와 같다  

 

3. 풀이

class Solution {
    var str = ""
    fun solution(s: String): Int {
        var answer = 1
 
        str = s
        for (len in s.length downTo 2) {
            for (startPoint in 0 until s.length - len) {
                if (checkP(startPoint, startPoint + len)) {
                    return len+1
                }
            }
        }
        return answer
    }
    
    fun checkP(startPoint: Int, endPoint: Int): Boolean {
        var sP = startPoint
        var eP = endPoint
        while (sP < eP) {
            if (str[sP] != str[eP]) {
                return false
            }
            sP++
            eP--
        }
        return true
    }
}