배열에 여러 개의 문자열이 저장되어 있다고 가정해 봅시다. 우리가 해야 할 일은 이 문자열들 사이에서 가장 긴 공통 접두사(Longest Common Prefix)를 찾는 것입니다. 이번 문제에서는 모든 문자열이 소문자로만 이루어져 있다고 가정하며, 만약 공통 접두사가 하나도 존재하지 않는다면 빈 문자열("")을 반환하면 됩니다.
예를 들어 문자열 배열이 ["school", "schedule", "scotland"]과 같이 주어졌다면, 세 문자열 모두 앞부분에 "sc"가 포함되어 있으므로 가장 긴 공통 접두사는 "sc"가 됩니다.
문제 해결 접근 방식
이 문제를 해결하는 방법은 다음과 같습니다.
- 배열의 첫 번째 문자열을 기준 문자열(current)로 설정합니다.
- 나머지 문자열들을 하나씩 가져와서 기준 문자열과 한 글자씩 비교합니다.
- 두 문자가 같으면 다음 글자로 넘어가고, 다르면 반복을 중단합니다.
- 비교가 끝난 후 일치한 부분까지의 부분 문자열로 기준 문자열을 갱신합니다.
- 모든 문자열에 대해 이 과정을 반복하면 최종적으로 남은 문자열이 곧 가장 긴 공통 접두사입니다.
파이썬 구현 예제
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
current = strs[0]
for i in range(1, len(strs)):
temp = ""
if len(current) == 0:
break
for j in range(len(strs[i])):
if j < len(current) and current[j] == strs[i][j]:
temp += current[j]
else:
break
current = temp
return current
input_list = ["school", "schedule", "scotland"]
ob1 = Solution()
print(ob1.longestCommonPrefix(input_list))입력
["school", "schedule", "scotland"]
출력
"sc"
코드 설명 및 시간 복잡도
위 코드는 먼저 입력 배열이 비어 있는 경우를 처리하기 위해 빈 문자열을 반환합니다. 그런 다음 첫 번째 문자열을 기준으로 삼고, 두 번째 문자열부터 순차적으로 비교를 진행합니다. 내부 반복문에서 각 위치의 문자가 서로 일치하는 동안만 결과를 누적하고, 불일치가 발생하는 즉시 반복을 종료합니다.
이 알고리즘의 시간 복잡도는 O(S)입니다. 여기서 S는 배열 내 모든 문자열의 문자 개수의 합입니다. 최악의 경우 모든 문자열이 완전히 동일할 때 전체 문자를 비교해야 하기 때문입니다. 공간 복잡도는 접두사를 저장하기 위한 임시 변수 때문에 O(1)로 볼 수 있습니다.
또한 실무에서는 파이썬의 os.path.commonprefix() 함수나 zip()과 set()을 활용한 파이썬다운(Pythonic) 방식으로도 간결하게 구현할 수 있다는 점도 참고하면 좋습니다.