[LeetCode, Kotlin] 14. Longest Common Prefix 풀어보기

문제

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

Input: strs = ["flower","flow","flight"]
Output: "fl"

 

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
    
    }
}

처음에 prefix 라는 단어를 놓쳐서 문제를 보자마자 기겁했었습니다.

전 배열에 공통적으로 포함되어 있는 (자리가 상관없는) String 중 가장 긴 거 찾기 인 줄 알았습니다..

다행히 시작 위치는 앞에서부터 고정입니다.

 

나의 풀이

문제를 보고 필요한 기능들을 정리해봤을 때,

1. 빈 값과 null 예외처리
2. Parameter 로 들어온 배열 중에서 가장 length 가 짧은 String 찾기
3. 반복문으로 prefix 찾기
4. 조건에 부합하는 값 리턴

이렇게 구성할 수 있었습니다.

class Solution14 {
    fun longestCommonPrefix(strs: Array<String>): String {
        var result = ""

        // 배열이 비어있으면 "" return
        if (strs.isNotEmpty()) {
            /*
             배열 중에서 가장 길이가 적은 것을 쓰고 싶었지만
             또 for 문 써야하기 때문에 strs[0] 으로 대체
             */
            val strSample: String = strs[0]

            for (i in 0..strSample.length) {
                // t , te, tes, test 순으로 올라감
                val test = strSample.substring(0, i)

                /*
                 이 for 문을 통과하면 모든 str에 동일한 prefix
                 */
                for (str in strs)
                    if (!str.startsWith(test))
                        return result

                result = test
            }
        }

        return result
    }
}

풀이 시작 전 구성한 내용대로 하다가

2번 삭선 된 내용은 사실 가장 길이가 짧은 String이 아니어도 크게 상관이 없었습니다.

그래도 다른 문제에서 '배열 중 가장 길이가 짧은 순으로 정렬' 이 필요할 수도 있겠다 싶어서 정리해보았습니다.

/* [## 임의로 맨 앞에 말고 확실하게 가장 작은 str 값을 쓰려면? ##] */
val comparator : Comparator<String> = compareBy { it.length }
val strOrdered = strs.sortedWith(comparator)    // sort의 시작복잡도 : O(nlogn)
val shortestStr = strOrdered[0]

 

또다른 풀이방법

사이트에서 분할정복(Divide and Conquer) 방식으로 풀이한 내용도 있어서 추가하고자 합니다.