Leetcode #14 Longest Common Prefix

문제

strs은 단어가 담긴 배열입니다.

공통된 시작 단어(prefix)를 반환해주세요.

예를 들어

strs = ['start', 'stair', 'step']
return은 'st'

strs = ['start', 'wework', 'today']
return은 ''

나의 풀이

처음엔 이 로직으로 시작을 했다.

• for문과 startswith으로 strs리스트 첫번째 단어 첫번째 알파벳 (문자열슬라이스 사용)
• for i in 문자열 -> i는 문자열의 1번째
• 딕셔너리에 저장 ex) prefix {'s' : True , 'st' : True}
• all 함수 로 딕셔너리 False 나오면 딕셔너리 마지막 key값 반환
• -> all 함수 if/break문
• 딕셔너리가 존재하지 않으면 '' 반환

코드를 작성하다가 비교한 단어의 value를 True로 딕셔너리에 저장하는 것에 막혔고 새로운 방법이 없나 생각해보았다. 그리고 코드를 완성한다고 하더라도 for문을 써서 전체를 비교하는 것에서 codekata#1처럼 시간복잡도에 문제가 생길 수 있다고 생각했다.
그러다가 생각한 것이 sort()함수였다. sort()를 사용할 경우에는 리스트 안의 요소를 알파벳순으로 정렬을 하므로, 첫 번째 인덱스의 문자열을 prefix의 기준으로 삼고, 마지막 단어를 for문을 사용해서 비교하면 된다는 생각이 났다.

def get_prefix(strs):
    prefix = ''
    if len(strs) == 0:	# 공통 단어가 없을 경우 '' 반환
      return prefix

    strs.sort() # strs 정렬
    for i in strs[0]:	#첫 번째 인덱스의 문자열
      if strs[-1].startswith(prefix+i):	# 마지막 인덱스의 문자열 차례대로 비교, 
        prefix += i	# 공통된 단어로 시작할 경우에 첫 번째 인덱스의 다음 문자열 추가
      else: # 공통된 단어가 없을 경우 for문을 빠져나옴
        break

    return prefix

처음에는 sort() 함수가 알파벳 순서가 아니라 문자열의 길이를 기준으로 정렬을 한다고 생각했다.
예를 들어 strs가 ['abc', 'qwe','abcd'] 인 경우에는 공통된 단어가 없음에도 True가 반환되는줄 알아서 for문을 하나 더 추가를 해야되나 고민을 했었다.
이번 문제를 풀면서 빌트인 함수의 동작을 정확하게 이해해야 한다는 중요성을 깨달았다.