⭐️ LeetCode 알고리즘 풀이 (with Python)

# Merge Two Sorted Lists

[Quetion]

LeetCode 21. Merge Two Sorted Lists

📌 접근법

[문제 이해]

• 두 개의 정렬된 연결 리스트를 이어야하며, 오름차순으로 정렬되어야 한다.

두 리스트 값을 순서대로 저장하기 위한 더미리스트를 생각했다.
그리고 만약 두 연결 리스트 중 한쪽이라도 Null 값이면 Null이 아닌 리스트 자체를 반환하면 되겠다고 판단했다.

💻 구현

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        # 더미 리스트, 현재 포인터 생성
        dummy = ListNode(0)
        current = dummy
        
        # 리스트 서로가 없으면 크로스 반환 
        if list1 is None:
            return list2
        if list2 is None:
            return list1

        while list1 and list2:
            # 리스트1 데이터가 클 경우 
            if list1.val > list2.val:
                # 더미에 list2 연결
                current.next = list2
                # 리스트2는 다음 연결로 이동
                list2 = list2.next

            # 리스트2 데이터가 클 경우
            else:
                # 더미에 list1 연결
                current.next = list1
                # 리스트1은 다음 연결로 이동
                list1 = list1.next
            
            # 더미 리스트도 다음 연결로 이동
            current = current.next
        
        # 마지막 노드 지정
        if list1 is None:
            current.next = list2
        else:
            current.next = list1

        return dummy.next

Runtime: 14ms | Memory: 13.3MB
LeetCode 코드 중 Runtime 93%, Memory 46% 해당하는 결과

📝 Merge Two Sorted Lists 회고

• 마지막으로 연결되는 값은 두 연결 리스트 중 하나라도 None일 경우 반복문을 탈출하기 때문에 두 연결 리스트 중 None이 아닌 리스트를 연결 해주도록 구현했다.

• Runtime은 93%로 빠른편에 속하기 때문에 개선을 할지 고민했는데, 조건문 분기가 많아서 코드가 복잡해 보이기에 조금 더 간결히 줄여보고자 여러 솔루션을 찾아서 적용시켜보았다.

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        current = dummy
        
        while list1 and list2:
            if list1.val > list2.val:
                current.next = list2
                list2 = list2.next
            else:
                current.next = list1
                list1 = list1.next
            current = current.next
        
        current.next = list1 or list2
        return dummy.next

Runtime: 14ms ---> 17ms
Memory: 13.3MB ---> 13.1MB

성능적으로는 같다고 볼 수 있지만 조건문 분기를 제거함으로써 코드의 가독성을 개선하는 효과를 얻었다.

원래 있던 리스트가 서로 없으면 크로스로 반환하는 if문은 사실상 중복되는 코드였다. 리스트가 하나라도 없을 경우 while문을 실행하지 못하고, 아래의 조건문을 or 연산자로 바꾸면 해당 코드를 실행하면 되기 때문에 제거하는 것이 맞았다.

---

# Search Insert Position

[Quetion]

LeetCode 35. Search Insert Position

📌 접근법

[문제 이해]

• target이 배열내에 있으면 그 값의 인덱스를 반환한다.
• 없을 경우 target이 삽입되어야 할 위치의 인덱스를 반환한다.
• 시간복잡도가 최소 O(log n) 보다 빨라야한다.

target에 해당하는 값을 반복문으로 배열을 탐색하면 되는 간단한 문제이지만, 시간복잡도가 O(log n)의 제한이 있기 때문에 일반적으로 반복문으로 탐색하게 되면 O(n)의 시간복잡도를 가지게 된다.

그래서 이진검색 방법을 통해 반복문의 반복횟수를 줄여서 O(log n)의 시간복잡도를 만족시켜야겠다고 생각했다.

생각의 흐름은 다음과 같이 구성하고 이를 토대로 구현을 해보았다.

1. 왼쪽, 오른쪽 포인터 생성

2. nums만큼 반복하는데

3. 평균 = (왼쪽 + 오른쪽) // 2

4. 평균 값이 target과 같으면 평균을 반환

5. 만약 평균 값이 > target이면

6. 오른쪽 = 평균 - 1

7. 그 반대이면 왼쪽 = 평균 + 1

💻 구현

class Solution(object):
    def searchInsert(self, nums, target):
        left, right = 0, len(nums)-1

        for i in range(len(nums)):
            avg = (left+right)//2
            
            if nums[avg] == target:
                return avg

            if nums[avg] > target:
                right = (avg-1)
            
            if nums[avg] < target:
                left = (avg+1)

        return left

Runtime: 32ms | Memory: 14MB
LeetCode 코드 중 Runtime 57%, Memory 37% 해당하는 결과

📝 Search Insert Position 회고

• 처음에는 오류가 발생해서 테스트 케이스를 통과히지 못했다. 분명 생각대로라면 나지 않아야 할 오류가 생겨서 생각이 잘못되었는지 확인하고 있었다.

• 결론적으로 nums[avg] 즉 평균 값을 인덱스로 가지는 nums의 값을 target과 비교해야하는데 평균을 그대로 target과 비교했으니 오류가 날 수 밖에 없던 것이다.

• 문제의 의도대로 O(log n)의 시간복잡도를 가졌고, 다른 풀이도 현재 코드와 같거나 비슷하기 때문에 추가적인 개선 사항은 떠오르지 않아서 수정하지 않았다.

---

# Search a 2D Matrix

[Quetion]

LeetCode 74. Search a 2D Matrix

📌 접근법

[문제 이해]

• 행렬의 각 행이 내림차순으로 정렬되었다.
• 각 행의 첫번째 값은 이전 행의 마지막 값 보다 크다.
• target 값이 행렬 내에 있으면 True, 없으면 False 반환
• 시간복잡도 O(log m*n)

문제를 읽고 두가지의 접근법이 생각났다.

첫번 째는 파이썬의 in 연산자로 for문을 돌며 확인하는 법

두번 째는 "각 행의 첫번째 값은 이전 행의 마지막 값 보다 크다"에서 힌트를 얻었다. 리스트 내의 리스트라는 점만 제외하면 오름차순으로 정렬된 하나의 리스트와 같다는 것이고, 이진 검색을 통해 해결하면 되겠다는 생각을 했다.

💻 구현

# 첫번째 구현 
class Solution(object):
    def searchMatrix(self, matrix, target):
        for i in range(len(matrix)):
            if target in matrix[i]:
                return True
        return False

Runtime: 93ms | Memory: 13.8MB
LeetCode 코드 중 Runtime 93%, Memory 10% 해당하는 결과

문제에서는 시간복잡도 O(log m*n)에 해당하는 코드를 작성해야해서 for문의 반복횟수를 줄이고자 했다.

for문은 행의 갯수에 따라 반복하며 한 행마다 target값이 있는지 in 연산자를 통해 확인하고 값을 반환한다.

문제는 해결상태로 통과되었으나, python의 in 연산자는 O(n)의 시간복잡도를 가지고 있다고 알고있는데 어떻게 통과를 하게 된건지 잘 모르겠다. 그래서 2번째 방법으로도 구현해보았다.

# 두번째 구현 - 이진 검색
class Solution(object):
    def searchMatrix(self, matrix, target):
        matrix=sum(matrix,[])
        l,r=0, len(matrix)-1

        while l <= r:
            avg = (l+r)//2

            if matrix[avg] == target:
                return True
            if matrix[avg] < target:
                l = avg + 1
            else:
                r = avg - 1

        return False

Runtime: 24ms | Memory: 13.7MB
LeetCode 코드 중 70Runtime %, Memory 30% 해당하는 결과

sum()함수로 행렬을 하나의 리스트로 합치고, L과 R포인터를 활용하여 이진검색을 했다.

이진검색은 Search insert position와 접근 방법이 똑같기 때문에 코드도 유사했다.

📝 Search a 2D Matrix 회고

• 처음 시도한 in 연산자 활용법과 다음으로 시도한 이진검색 방법 중 솔루션에서는 이진검색 방법을 많이 사용하고 있었다.

• 테스트 케이스의 차이에 따라 달라질 수 있지만 두 구현 방법 모두 성능적으로는 비슷한 결과를 얻을 수 있었다.

• in 연산자를 활용한 구현법은 현재도 간결한 코드라 더 이상 개선할 방법이 떠오르지 않는다.

• 이진 검색으로 구현한 코드에서는 sum()함수를 사용하지 않고, 원래의 행렬 상태에서 조건문을 변경하면 시간복잡도를 조금 더 개선할 수 있지 않을까? 라는 생각이 들었다. 하지만 그만큼 코드도 늘어나고, 새로운 변수도 생성되어야 할 것 같아서 개선 효과는 미미할 것 같다.