[5일차] TIL (문자열 다루기)

알고리즘 주차 시작

알고리즘 강의를 듣고 과제(문자열 조작 / 배열)를 푸는 식 이었습니다.

 

오전 중으로 강의를 다 듣고 8시 발표 전까지 과제를 다 풀어야했고 다음은 과제 내용입니다.

 

1. 그룹 애너그램 

https://leetcode.com/problems/group-anagrams/

처음에는 다음과 같이 이중 for문을 돌려서 비효율적으로 접근 했습니다.

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        new_strs = []
        temp = []
        for word in strs:
            # sort() vs sorted()
            sort_word = sorted(word)
            sort_word = ''.join(sort_word)  # 알파벳 순으로 정렬
            new_strs.append(sort_word)  # result라는 배열에 저장 []
            if sort_word not in temp:
                temp.append(sort_word)

        # strs = ["eat","tea","tan","ate","nat","bat"]
        # new_strs = ['aet', 'aet', 'ant', 'aet', 'ant', 'abt']
        # temp = ['aet', 'ant', 'abt']

        answer = [[] for _ in range(len(temp))]

        for i in range(len(strs)):
            for j in range(len(temp)):
                if new_strs[i] == temp[j]:
                    answer[j].append(strs[i])

        return answer

 

 

더 효율적인 풀이로는 defaultdict라는 라이브러리를 import 해오면 배열 초기화 없이 배열을 다룰 수 있다는 점이 장점입니다.

from collections import defaultdict
    
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        
        for word in strs:
            # 정렬하여 딕셔너리에 추가
            anagrams[''.join(sorted(word))].append(word)
        print(anagrams)
        return list(anagrams.values())

 

 

2. 가장 긴 팰린드롬 부분 문자열

https://leetcode.com/problems/longest-palindromic-substring/

이 문제를 보고 감조차 잡지 못했습니다.

 

답안지 풀이

def longestPalindrome(s: str) -> str:
    def expand(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    # 해당 사항이 없을 땐 빠르게 리턴
    if len(s) < 2 or s == s[::-1]:
        return s
    result = ''
    for i in range(len(s) - 1):
        result = max(result, expand(i, i + 1), expand(i, i + 2), key=len)
    return result

여기서 expand(i, i + 1)은 짝수개의 글자를 판별하고 expand(i, i + 2) 는 홀수개의 글자를 판별합니다.

 

 

 

3. 세 수의 합

https://leetcode.com/problems/3sum/

저는 우선 3개의 조합으로 된 경우의 수를 뽑아보기로 했습니다. 

뽑고 난 후 각 튜플로 된 원소들을 정렬하고 중복되는 것을 제거하면서 answer라는 리스트에 담았습니다.

 

아래 풀이는 내가 풀었지만 Memory Limit Exceeded

from itertools import combinations

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        data = list(combinations(nums, 3))
        answer = []
        for item in data:
            if sum(item) == 0:
                new_item = tuple(sorted(item, key=lambda x:x))
                if new_item not in answer:
                    answer.append(new_item)

        return answer

 

브루트 포스 풀이 (이 역시 Time Limit Exceeded)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()

        # 브루트 포스 n^3번 반복
        for i in range(len(nums) - 2):
            # 중복된 값 건너뛰기
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k - 1]:
                        continue
                    if nums[i] + nums[j] + nums[k] == 0:
                        results.append([nums[i], nums[j], nums[k]])
                    
        return results

 

 

시간 복잡도를 O(N^2)으로 줄인 풀이

def threeSum(nums):
    result = []
    nums.sort()

    for i in range(len(nums) - 2):
        # 중복값제거
        if i > 0 and nums[i] == nums[i - 1]:
            continue
            
        left, right = i + 1, len(nums) - 1
        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
                #찾게 되면 포인터 이동

    return result

 

 

4. 배열 파티션

https://leetcode.com/problems/array-partition-i/

두개 씩 pair로 묶은 후 각 pair의 최소값을 합했을 때 가장 큰 값을 찾는 문제입니다. 

우선 제일 처음 부터 2개씩 pair로 만드는 경우가 최소값들을 합쳤을 때 가장 큰 값이 되는데

아래처럼 item을 nums라는 배열을 2개씩 잘라 array라는 배열에 넣어준 후 배열을 돌며 최소값을 찾아 result에 합쳐서 return 하였습니다.

def arrayPairSum(self, nums: List[int]) -> int:
    nums.sort()
    array = []
    for i in range(0, len(nums), 2):
        item = nums[i:i + 2]
        array.append(item)
    result = 0
    for i in array:
        result += min(i)
    return result

 

답안지 풀이 1

def arrayPairSum(self, nums: List[int]) -> int:
    sum = 0
    pair = []
    nums.sort()

    for n in nums:
        # 앞에서부터 오름차순으로 페어를 만들어서 합 계산
        pair.append(n)
        if len(pair) == 2:
            sum += min(pair)
            pair = []

    return sum

 

답안지 풀이 2

def arrayPairSum(self, nums: List[int]) -> int:
    sum = 0
    nums.sort()

    for i, n in enumerate(nums):
        # 짝수 번쨰 값의 합 계산
        if i % 2 == 0:
            sum += n

    return sum

 

파이썬 다운 풀이

def arrayPairSum(self, nums: List[int]) -> int:
    return sum(sorted(nums)[::2])