LeetCode 14(Longest Common Prefix, Python)

1. 문제 링크

• Longest Common Prefix - LeetCode

Longest Common Prefix - LeetCode

2. 문제 설명

• 여러 문자열을 포함한 리스트가 주어졌을 때 모든 문자열의 앞에서부터 최대한 긴 공통 부분을 반환
• 예시) ["flower","flow","flight"]이면 "fl" 반환, strs = ["dog","racecar","car"]이면 "" 반환

3. 처음 풀이 

• 각 인덱스와 문자열에 대한 이중 for문을 돌려 같은 인덱스에서 문자열이 같으면 결과에 추가
• 먼저 각 문자열의 길이 중 최솟값을 구하여 인덱스 범위를 정함
  • minlen=min(strs, key=len)을 통해 바로 strs 리스트 안의 문자열 길이의 최솟값을 알 수 있다.
• 인덱스 i에 대해 각 문자열의 i 인덱스 문자가 같으면(각각을 집합에 추가하여 집합 원소가 1개이면 모두 같은 문자) 결과에 추가
• 다른 문자가 나오거나 for문이 끝나면 결과를 반환

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        result='' 
        lenset=set() #각 문자열의 길이를 보관
        
        for i in strs: #문자열 중 길이의 최솟값 찾기
            lenset.add(len(i)) #각 문자열의 길이를 lenset에 보관
        minlen=min(lenset) #lenset의 값 중 최솟값 찾기
        #이렇게 하지 말고 minlen = min(strs, key=len) 해도 됨.

        for i in range(minlen): #인덱스 i
            temp=set() #각 문자열의 i 인덱스 문자를 보관 
            for s in strs: #각 문자열에 대해
                temp.add(s[i]) #i 인덱스 문자를 집합 temp에 보관
            if len(temp)==1: #만약 모두 같은 문자라면 집합 temp 원소는 하나
                result+=temp.pop() #그렇다면 조건 만족하므로 결과에 그 문자를 추가하며 temp에서는 삭제
            else: #집합 temp의 원소 개수가 1개가 아니라면 공통이 아닌 문자가 등장
                return result #그때까지 만들어진 공통 부분을 반환
        return result

4. 다른 풀이 

• 'abc', 'abd', 'abe' 를 앞에서부터 짝지어 (a,a,a), (b,b,b), (c,d,e)를 반환해주는 함수 zip을 이용
• 두 개 이상의 iterable(반복 가능한) 객체를 가져와 해당 객체들의 원소를 순서대로 묶어 튜플로 만듦
• 객체들의 길이가 다르면 짧은 것 기준으로 만들고 남는 것은 버림
• * 연산자는 인자 언패킹 연산자로, iterable 내의 요소들을 개별 인수로 분해
• 문자열들이 담겨있는 리스트 strs을 *연산자로 unpacking 한 후 zip 함수를 이용하여 각 문자열의 문자를 순서대로 묶어 집합에 넣은 후 집합의 원소 개수가 1이면 모두 같은 문자이므로 결과에 추가

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ""
        for a in zip(*strs):
            if len(set(a)) == 1: 
                res += a[0]
            else: 
                return res
        return res

5. 배운 점 

• min, max 함수에 매개변수 key를 이용하면 원하는 값 기준으로 최소 최대 찾기

strings = ["apple", "banana", "cherry", "date", "fig"]
min_length_str = min(strings, key=len)
max_length_str = max(strings, key=len)

print("가장 짧은 문자열:", min_length_str)
print("가장 긴 문자열:", max_length_str)

def custom_key_function(item):
    return item["age"]

people = [
    {"name": "Alice", "age": 30},
    {"name": "Bob", "age": 25},
    {"name": "Charlie", "age": 35},
    {"name": "David", "age": 28}
]

youngest_person = min(people, key=custom_key_function)
oldest_person = max(people, key=custom_key_function)

print("가장 어린 사람:", youngest_person["name"])
print("가장 나이 많은 사람:", oldest_person["name"])

• * 연산자로 list 안의 요소들을 개별 인수로 분해한 후 zip 함수를 이용하여 두 개 이상의 iterable 한 객체를 가져와 해당 객체들의 원소를 순서대로 묶어 튜플로 반환

pairs = [(1, 'a'), (2, 'b'), (3, 'c')]
a, b = zip(*pairs)
print(a) #(1,2,3)
print(b) #('a','b','c')