LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 문자로 이루어진 배열 strs
2. output: 문자들의 공통된 접두어 중, 가장 긴 접두어 리턴

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

Idea

따로 시간 복잡도의 제한이 없었고, 배열의 크기도 200이하로 크지 않았기 때문에, 완전 탐색으로 접근하였다.

처음엔 startWith() 함수를 사용하였지만, startWith()의 경우 패턴의 길이만큼 매번 비교하므로 idx의 문자 1개만 같은지 확인하는 것이 더 효율적인 방법이다.

Solution

1. BruteForce

   배열의 첫번째 문자를 슬라이싱하여, 다른 모든 문자의 접두어가 되는지 확인

   → 모든 문자의 공통 접두어를 찾는 것이므로 배열의 어느 문자를 기준으로 하든 상관X

   class Solution {
       fun longestCommonPrefix(strs: Array<String>): String {
           var answer = ""
           for (i in 1..strs.map { it.length }.min()!!) {
               val pref = strs[0].substring(0,i)
   						// 배열의 모든 문자에서 접두어가 되는지 확인
               if (strs.filter { it.startsWith(pref) }.size == strs.size) answer = pref 
   						else break
           }
           return answer
       }
   }
   

   시간 복잡도: 최소 길이의 문자 순회 X 배열의 모든 문자 순회 = n^2

   

2. BruteForce

   모든 문자에서 공통되는 접두어를 찾는 것이므로 하나라도 아니면 종료 가능 → BackTracking

   1의 방법에서 모든 문자에서 접두어가 되는지 확인하지 않고, 안되는 경우 바로 리턴

   class Solution {
       fun longestCommonPrefix(strs: Array<String>): String {
           var answer = ""
   				// 접두어의 최대 길이는 배열에서 가장 짧은 문자의 길이
           for (i in 1..strs.map { it.length }.min()!!) {
               val pref = strs[0].substring(0,i) // 확인해 볼 접두어
               for (str in strs) {
   								// 접두어가 아니라면, 이전의 답 리턴
                   if (!str.startsWith(pref)) return answer
               }
               answer = pref // 최장 접두어 갱신
           }
           return answer
       }
   }
   

   시간 복잡도: 최소 길이의 문자 순회 X 배열의 모든 문자 순회 = n^2

   

3. BruteForce (idx를 증가하며, 문자 하나씩만 비교)

   class Solution {
       fun longestCommonPrefix(strs: Array<String>): String {
           var idx = 0
           // 접두어의 최대 길이는 배열에서 가장 짧은 문자의 길이
           while (idx < strs.map { it.length }.min()!!) {
               for (str in strs) {
                   // 접두어가 아니라면, 이전의 답 리턴
                   if (str[idx] != strs[0][idx]) return strs[0].substring(0, idx)
               }
               idx++ // 최장 길이
           }
           return strs[0].substring(0, idx)
       }
   }
   

   시간 복잡도: 최소 길이의 문자 순회 X 배열의 모든 문자 순회 = n^2

   

Point

1. 배열의 모든 원소를 순회하지 않고 돌아가는(Back) 경우가 1번 뿐이기 때문에, 1, 2 코드의 성능적 차이는 거의 없음