[프로그래머스] 가장 긴 펠린드롬 | kotlin - 미해결

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

풀이

class Solution {
    fun solution(s: String): Int {
        var answer = 1
        for (i in s.indices) {
            var subS = s.substring(i..s.length-1)
            if(subS.length < answer) break
            while(subS.length>0){
                val length = subS.length
                if(subS[0] == subS[length-1]){
                    if(subS == subS.reversed()){
                        answer = maxOf(answer, length)
                        break
                    }
                }
                subS = subS.dropLast(1)
            }
        }
        return answer
    }
}

효율성 1번만 시간초과가 나서 머리 쥐어 뜯다가..

아니 사실 substring, reversed를 쓰는 게 비효율 적이라는 생각은 들었지만 이걸 어찌해야할지 고민이 많았다.

길이가 긴 문자열 부터 비교를 하는게 맞다고 생각을 했고 bfs를 적용하면 쉽게 풀리지 않을 까 생각했다.

class Solution {
    fun solution(s: String): Int {
        var answer = 1
        val que = ArrayDeque<String>()
        que.addLast(s)

        while (que.isNotEmpty()) {
            val temp = que
            for(i in temp.indices){
                val value = que.removeFirst()

                if (palindrome(value)) {
                    return value.length
                }
                if (value.length > 2) {
                    que.addLast(value.dropLast(1))
                    que.addLast(value.drop(1))
                }
            }
        }
        return answer
    }

    fun palindrome(s: String): Boolean {
        var start = 0
        var end = s.length - 1
        for (i in 1..s.length / 2) {
            if (s[start] != s[end]) return false
            start++
            end--
        }
        return true
    }
}

하지만 while문이 돌아가면서 큐에는 2^n 개의 문자열이 쌓이고.. 메모리 초과가 떠버렸다...ㅜㅜ

bfs 생각하고 기가막히다는 생각이 들었는데 막상 코드를 짜보니 메모리 측면에서 매우매우 비효율 적인 코드가 완성이 되어버렸다......

 

결국 못참고 다른 사람의 풀이를 봐버렸는데 이걸 왜 생각을 못했지라는 생각이 들면서

지금 이대로 풀어버리면 그냥 베낀 코드가 되버릴것 같아서 나중에 다시 풀기로 결정했다..

 

화가난다 화가나

 

문제 링크