LeetCode - Longest Common Prefix

문제 링크 : https://leetcode.com/problems/longest-common-prefix/

난이도 : Easy

---

문제 풀이 :

주어진 문자열들이 공통으로 갖고 있는 가장 긴 접두어를 찾는 문제다.

가장 긴 접두어는 가장 짧은 문자열의 길이보다 작거나 같다는 것만 생각하면 어렵지 않게 풀 수 있다.

가장 짧은 문자열을 기준으로 모든 문자열들의 맨 앞부터 시작하여 공통으로 가지고 있는 것들을 더해가면 된다.

---

소스 코드 :

class LongestCommonPrefix {
    fun longestCommonPrefix(strs: Array<String>): String {
        if(strs.isEmpty()) return ""
        else if(strs.size == 1) return strs[0]

        val sortedStrs = strs.sortedBy { it.length }
        val stringBuilder = StringBuilder("")

        for (i in sortedStrs[0].indices) {
            val cur = sortedStrs[0][i]
            var isHasAllStr = true

            for (j in 1 until sortedStrs.size) {
                if(sortedStrs[j][i] != cur) {
                    isHasAllStr = false
                    break
                }
            }

            if(isHasAllStr) {
                stringBuilder.append(cur)
            } else {
                break
            }
        }

        return stringBuilder.toString()
    }
}

---

후기 : 

다른 사람들의 풀이를 보니 정렬을 하지 않고 더 빠른 정답을 찾아내는 것이 있었다. 보고나니 이해는 되었다.

또한 이분탐색을 이용하는 방법도 있던데 아직 이해는 못했다. 나중에 시간을 내어 다시 한번 봐야겠다.