[leetcode][파이썬]Longest Common Prefix #004

https://leetcode.com/problems/longest-common-prefix/description/

 

 

 

---

 

 

 

 

오늘 풀어본 문제는 " Longest Common Prefix" 이다.

주어진 리스트 안에 있는 문자열들 간에 가장 긴 공통 접두어를 출력하는 것이다.

 

 

풀이 #1 - Loop + Filter

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        minStr = min(strs, key=len)

        if len(strs) == 0 or len(strs) == 1 or len(minStr) == 0: return minStr
        for i in range(len(minStr)):
            filterList = list(filter(lambda n: n[i] != minStr[i] , strs))
            if len(filterList) > 0: return minStr[:i]
        
        return minStr

 

내가 고안한 방식은 가장 길이가 적은 문자열을 기준으로 해당 길이만큼 반복을 하면서 필터(filter) 기능을 사용하고 싶었다. 겸사겸사 filter 사용법에 람다함수를 이용하는 법도 알게되어서 코드에 적용을 해보았다.

 

 

 

풀이 방식

1. 주어진 strs(리스트) 안에서 가장 짧은 길이의 문자열을 minStr라고 선언

2. strs(리스트) 길이가 0이거나 1이거나 minStr 길이가 0이거나 했을 때, minStr을 반환

- 내가 짠 코드들은 여러 조건들로 구성돼 있지만 이 부분을 아래와 같이 단순하게 수정해 리스트 내부 값을 확인할 수 있었다.

if not strs:
	return ""

  

3. minStr 길이만큼 순환하는 반복문 내에 filter 함수를 이용해 minStr과 비교값과 불일치하는 값 리스트를 구함

4. 만약 filter에서 반환된 list 길이가 0보다 크다면, 즉 불일치하는 값이 발생했을 때 인덱스 값을 이용해 기준값(minStr)을 슬라이싱해서 반환

5. 반복문 종료 후, 불일치하는 값이 없을 경우 기준값 반환

- 불일치하는 값은 없지만 중복되는 값을 가진 값들이 존재한다는 것이기 때문에 minStr를 반환하였다.

 

 

 

 

 

 

풀이#1 - 최적화

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        minStr = min(strs, key=len)

        for i, char in enumerate(minStr):
            for string in strs:
                if string[i] != char:
                    return minStr[:i]
        
        return minStr

 

 

 

 

 

 

최적화한 부분

1. 입력 리스트가 비어 있거나 하나의 문자열만 있는 경우, 또는 최소 문자열 길이가 0인 경우 

 

Before

    if len(strs) == 0 or len(strs) == 1 or len(minStr) == 0: return minStr

 

After

if not strs:
    return ""

 

 

2. filter 기능대신 이중 for문으로 대체 (직접 비교)

- filter 함수 사용 시, 매 루프마다 새로운 리스트 생성에 대한 불필요한 메모리 사용과 연산 초래

 

Before

for i in range(len(minStr)):
    filterList = list(filter(lambda n: n[i] != minStr[i] , strs))
    if len(filterList) > 0: return minStr[:i]

 

 

After

for i, char in enumerate(minStr):
    for string in strs:
        if string[i] != char:
            return minStr[:i]

 

 

 

 

 

알게된 점

- 파이썬답게 인덱스와 원소를 동시에 접근하면서 루프를 돌릴 수 있는 파이썬 내장 함수인 enumerate()를 알게 됨

- if ~ not in 사용하여 리스트에서 특정 요소의 포함 여부를 확인할 수 있음