항해99 알고리즘 1회차

그룹 애너그램 - https://leetcode.com/problems/group-anagrams/

 

나의 접근 방식

1. 입력된 문자를 반복 해준다.

2. 없을경우 새로 만든 배열에 넣어주고, 있으면 문자 비교 후 기존 배열에 담아준다.

3. 2차원 배열 내 문자를 정렬 후, 개수로 재정렬을 한다.

 

회고

1. defaultdict(list)를 사용하면 존재하지 않는 키여도 접근하면 자동으로 생성

2. 정렬을 하면 key 값이 같기 때문에 key, value 형식으로 값을 넣어주고

3. list로 변환시켜서 속도가 매우 빨라짐

 

기존에는 반복문을 사용해서 일일이 비교 후 넣었지만, 키값으로 넣어줘서 list로 변환하여 속도가 매우 단축됐습니다.

 

틀린 예제 - 테스트 케이스는 통과하였지만, 시간초과로 틀렸습니다.

# 테스트 케이스
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

strsArr = []

# 문자를 반복
for s in strs:
    tempArr = [s]
    if len(strsArr) == 0:
        strsArr.append(tempArr)
    else:
        # 저장된 문자를 반복
        count = 0
        for x in range(len(strsArr)):
            if ''.join(sorted(strsArr[x][0])) == ''.join(sorted(s)):
                strsArr[x].append(s)
                count = 1

        if count == 0:
            strsArr.append(tempArr)

strsArr = sorted(strsArr)
sortStrsArr = [sorted(row) for row in strsArr]
print(sorted(sortStrsArr, key=len))

 

맞은 예제 - GPT

from collections import defaultdict

def group_anagrams(strs):
    # 그룹 애너그램을 저장할 딕셔너리
    anagram_groups = defaultdict(list)

    # 각 문자열을 정렬하여 정렬된 문자열을 키로 사용하여 그룹화
    for word in strs:
        sorted_word = ''.join(sorted(word))
        anagram_groups[sorted_word].append(word)

    # 결과를 리스트의 리스트로 변환
    result = list(anagram_groups.values())

    return result

# 예제 사용
input_strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
result_groups = group_anagrams(input_strs)
print(result_groups)

---

가장 긴 팰린드롬 부분 문자열 - https://leetcode.com/problems/longest-palindromic-substring/

 

나의 접근 방식

1. 바로 옆에 가까운 문자를 찾는다.

2. 모든 문자의 위치를 찾았으면 역정렬을 하여 빼준다.

2-1. 뺀 값의 제일 큰 값의 문자열의 index를 저장한다.

3. 그중 제일 큰 값의 문자를 보여준다.

 

해당 접근 방식으로 하였지만 도저히 못 풀어서 해답을 확인

Manacher's Algorithm 사용하여서 찾아야 하는 문제였다.

 

회고

재공부가 필요하다.

 

맞은 예제 - GPT

def longestPalindrome(s: str) -> str:
    # 가상의 문자 추가
    modified_s = '#'.join('#' + s + '#')

    # 팰린드롬 반경 배열 초기화
    n = len(modified_s)
    radius = [0] * n

    # 중심과 우측 경계 초기화
    center, right = 0, 0

    max_radius, max_center = 0, 0

    for i in range(n):
        if i < right:
            mirror = 2 * center - i
            radius[i] = min(right - i, radius[mirror])

        # 팰린드롬 확장
        a, b = i + (1 + radius[i]), i - (1 + radius[i])
        while a < n and b >= 0 and modified_s[a] == modified_s[b]:
            radius[i] += 1
            a += 1
            b -= 1

        # 중심과 우측 경계 갱신
        if i + radius[i] > right:
            center, right = i, i + radius[i]

        # 최장 팰린드롬 갱신
        if radius[i] > max_radius:
            max_radius, max_center = radius[i], i

    # 최장 팰린드롬을 가져옴
    start = (max_center - max_radius) // 2
    end = start + max_radius
    return s[start:end]


print(longestPalindrome("babad"))

---

세 수의 합 - https://leetcode.com/problems/3sum/

 

나의 접근 방식

- 30분 생각해봤지만 생각이 안 남

 

회고

투 포인터를 사용하여 문제를 풀어야 했다.

left 값을 올려주고 right 값을 내려주면서 0일 때 배열에 append 해준다.

    - 투 포인터는 정렬을 했을 때 효과적이라고 한다, 정렬을 안 하고 사용하는 상황도 있다.

left, right 에도 중복을 확인하면서 넘어간다.

 

맞은 예제 - GPT

def threeSum(nums):
    result = []
    nums.sort()  # 배열을 정렬
    for i in range(len(nums) - 2):  # 배열 길이가 3개 초과 할 때 작동을 한다.
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # 중복된 값을 피하기 위한 조건 (정렬을 했기 때문에 가능)

        left, right = i + 1, len(nums) - 1  # 투 포인터 초기화

        while left < right:  # 오른쪽 포인터가 클 경우 계속 반복
            total = nums[i] + nums[left] + nums[right]

            if total < 0:
                left += 1
            elif total > 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

print(threeSum(nums=[-1, 0, 1, 2, -1]))

---

배열 파티션 - https://leetcode.com/problems/array-partition/

 

나의 접근 방식

1. 배열의 숫자들을 n2로 하나하나 2개씩 그룹화하여 계산

 

회고

위의 나의 접근 방식은 매우 잘못 생각했다, 그룹 최댓값만 구하면 되기 때문에 정렬 후 그룹화해서 계산하면 됐음

 

맞은 예제 - GPT

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


nums = [1, 4, 3, 2]
print(arrayPairSum("", nums))