문제 소개
소문자로만 이루어진 문자열 목록이 주어졌을 때, 목록의 모든 문자열에 공통으로 포함되는 가장 긴 접두사, 즉 최장 공통 접두사(longest common prefix)를 찾아야 합니다.
예를 들어 입력이 ["antivirus", "anticlockwise", "antigravity"]라면 세 문자열이 모두 "anti"로 시작하므로 결과는 "anti"가 됩니다.
풀이 전략
핵심 아이디어는 한 문자열을 기준으로 삼아 한 글자씩 추가해 가면서, 나머지 모든 문자열과 해당 위치의 문자가 일치하는지 검증하는 것입니다. 단 하나의 문자라도 어긋나면 그 앞부분까지가 곧 최장 공통 접두사입니다. 구체적인 단계는 다음과 같습니다.
- 정렬: words 목록을 알파벳순으로 정렬합니다.
- 초기화: prefix := 새로운 빈 리스트, flag := 0으로 설정합니다.
- 문자 추가 및 검증: i를 0부터 words[0]의 길이까지 반복하면서 다음을 수행합니다.
- words[0]의 i번째 문자를 prefix에 추가합니다.
- words의 각 문자열 j에 대해 j[i]가 prefix의 마지막 문자와 같은지 확인합니다.
- 하나라도 다르면 prefix에서 마지막 문자를 제거하고 flag := 1로 설정한 뒤 내부 반복문을 종료합니다.
- 조기 종료: flag가 1이면 더 이상 진행할 필요가 없으므로 바깥쪽 반복문도 즉시 종료합니다.
- 결과 반환: prefix 배열의 모든 문자를 이어 붙인 문자열을 반환합니다.
구현 코드
위 알고리즘을 파이썬으로 구현한 예제는 다음과 같습니다.
class Solution:
def solve(self, words):
words.sort()
prefix = []
flag = 0
for i in range(len(words[0])):
prefix.append(words[0][i])
for j in words:
if j[i] != prefix[-1]:
prefix.pop()
flag = 1
break
if flag == 1:
break
return ''.join(prefix)
ob = Solution()
words = ["antivirus", "anticlockwise", "antigravity"]
print(ob.solve(words))
실행 결과
입력:
["antivirus", "anticlockwise", "antigravity"]
출력:
anti
코드 동작 과정 상세
목록을 정렬하면 ["anticlockwise", "antigravity", "antivirus"] 순서가 됩니다. 이후 인덱스 0부터 3까지의 문자 'a', 'n', 't', 'i'는 세 문자열이 모두 일치하므로 prefix에 차례대로 쌓입니다. 그러나 인덱스 4에서 "anticlockwise"는 'c'인 반면 "antigravity"는 'g'로 서로 다르므로, 해당 문자는 prefix에서 제거되고 flag가 1로 설정되면서 반복문이 종료됩니다. 최종적으로 prefix에는 ['a', 'n', 't', 'i']만 남아 "anti"가 반환됩니다.
복잡도 분석
문자열의 개수를 n, 가장 짧은 문자열의 길이를 m이라 하면 비교 단계의 시간 복잡도는 O(n × m)입니다. 여기에 초기 정렬 비용이 추가되지만, 실제로는 정렬 없이 임의의 기준 문자열 하나를 골라 나머지 문자열들과 비교해도 동일한 결과를 얻을 수 있으므로 정렬은 생략해도 무방합니다.