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

# Linked List Cycle

[Quetion]

LeetCode 141. Linked List Cycle

📌 접근법

[문제 이해]

• Linked List에서 순환이 있는지 확인
• next 노드가 있는 경우 순환이 있는 것으로 판단
• 순환이 있으면 True, 없으면 False

이전 원티드 강의에서 토끼와 거북이 알고리즘을 응용하면 Linked List에 순환이 있는지 판단할 수 있다고 한 것을 기억하고, 토끼와 거북이 포인터를 활용한 접근 법으로 생각해보았다.

1. 빠른 이동, 느린 이동 포인터를 생성

2. 느린 포인터를 한 칸 이동

3. 느린 포인터가 없으면 = 도달 = 순회X

4. 빠른 포인터 한 칸 이동

5. 빠른 포인터가 없으면 = 도달 = 순회X

6. 빠른 포인터 한 칸 더 이동

7. 두 노드가 만나면 = 순회 O

8. 둘 중 하나라도 Null이면 순회X

💻 구현

class Solution(object):
    def hasCycle(self, head):
    	# 현재(빠른 포인터)
        current=head
        # 느린 포인터
        slownode=head

        while current and slownode:
        
            slownode=slownode.next
            
            if slownode is None:
                return False
                
            current=current.next
            
            if current is None:
                return False
                
            current=current.next
            
            if current == slownode:
                return True
        
        return False

Runtime: 39ms | Memory: 20.4MB
LeetCode 코드 중 Runtime 53%, Memory 29% 해당하는 결과

📝 Linked List Cycle 회고

• 두 개의 포인터 중 하나는 빠르게, 하나는 느리게 다음으로 이동하는 것이 핵심인 토끼와 거북이 알고리즘을 활용한 방법들이 많았다.
• 그 중 이 코드는 조건문을 통해 항상 두 포인터가 도달했는지, 그렇지 않은지 확인하는데 이 과정에서 조건문의 분기가 많이 생겼다.

다른 솔루션을 찾아보니 이러한 조건문을 없앨 수 있었다.
예외처리로 순회가 없다는 판단을 할 수 있다는 것을 알게 되었고 이를 적용 해보았다.

class Solution(object):
    def hasCycle(self, head):
        try:
            current=head.next
            slownode=head
			
            # if current == slownode: return True와 의미 동일
            while slownode is not current:
                slownode = slownode.next
                current = current.next.next
            return True

		# slownode or current is None과 의미 동일
        except:
            return False

Runtime: 39ms ---> 28ms
Memory: 20.4MB ---> 20.4MB

try except 구문은 백엔드 로직에서 에러 처리를 할 때 주로 사용했었는데, 기존 코드를 이렇게 바꿀 수 있다는 점이 신선했다. 왜 이 생각을 하지 못했을까..?

여기서 핵심은 True 혹은 False의 조건이 둘 중 하나는 단일 조건이어야 try except구문으로 예외처리가 쉬울 것 같다는 것이다. 결과적으로 코드도 이전 보다 간결해지고, Runtime 또한 11ms의 개선 효과를 얻을 수 있었다.

return type이 True와 False로 나뉘고 해당 문제처럼 간단한 분기로 나뉠 때, try except 구문으로 분기를 묶어 줄 수 있다는 것을 깨닫게 되었고 성능 또한 여러 분기 보다 조금 더 빠를 수 있다는 것을 알게 되었다.

---

# Add Two Numbers

[Quetion]

LeetCode 2. Add Two Numbers

📌 접근법

[문제 이해]

• 두개의 노드가 있고, 각 두 노드의 값은 역순으로 되어있다.
• 두 노드의 값을 합한 합계를 연결 리스트로 반환하면 된다.
• [2,4,3], [5,6,4] 이면 342 + 465 = 807이므로 [7,0,8] 반환

두 노드 값의 합이 10이 넘어갈 때, 십의 자리 수를 저장할 새로운 노드가 필요하다고 생각했다.

또한 처음에는 더미 노드 하나를 더 추가하여 두 노드 값의 합을 저장하는 노드를 만드려고 했으나, 코드도 복잡하고 오류 상황이 많이 발생하여 새로운 노드가 아닌 변수에 더해가는 방법을 생각해보았다.

1. 더미 노드, 각 노드 val의 합을 저장할 변수 생성

2. L1, L2, 변수 중 하나라도 존재하면 반복하는데

3. 만약 L1이 none이 아니면 변수 += L1.val
   L1을 다음 노드로 이동

4. 만약 L2가 none이 아니면 변수 += L2.val
   L2를 다음 노드로 이동

5. 더미의 다음 노드에 L1.val + L2.val을 더한 1의 자리 값을 반환

6. 더미 노드를 다음 노드로 이동

7. 저장한 val을 10으로 나눔 == L1.val + L2.val >= 10일 경우, 십의 자리 수를 남김

💻 구현

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy=ListNode(0)
        current = dummy
        save = 0 

        while l1 or l2 or save:
            if l1 is not None:
                save+= l1.val
                l1 = l1.next
            
            if l2 is not None:
                save+= l2.val
                l2 = l2.next
            
            current.next = ListNode(save%10)
            
            current = current.next

            save = save//10
        return dummy.next

Runtime: 28ms | Memory: 13.2MB
LeetCode 코드 중 Runtime 99%, Memory 87% 해당하는 결과

📝 Linked List Cycle 회고

• 처음에는 더미 노드 2개로 같은 의미의 코드를 구현해보려고 시도했으나 L1 혹은 L2가 None일 경우의 오류 상황을 잡기 힘들어서 더미 노드 1개와 변수를 활용해보았다.

• 그리고 if L1.val==0 and L2.val==0: return L1 구문을 통해 L1과 L2가 0값이면 둘 중 아무 값이나 반환 하는 코드를 추가했었으나, L1=[0,1,2~], L2=[0,4,2~]의 예외상황이 있어서 제거하게 되었다.

• save에 저장한 값은 9+9 즉, 최대 18이므로 앞자리가 2를 넘길 수 없기 때문에 10을 기준으로 잡고 나머지와 몫을 구하는 연산을 했다. 그래서 val의 합이 10이상일 경우 10의 자리를 넘겨서 나머지와 함께 더해지는 것을 표현할 수 있었다.

• 다른 솔루션들도 더미노드를 많이 활용했고, 코드 또한 비슷하여 추가 개선은 진행하지 않았다.

---