연결 리스트

연결 리스트를 이어서 공부해보았다.

LeetCode 2.Add Two Numbers

역순으로 저장된 연결 리스트의 숫자를 더하라.

Solution 1 자료형 변환

연결 리스트를 문자열로 이어 붙인 후 숫자로 변환하여 이를 계산하고, 다시 연결 리스트로 바꾸면 쉽게 풀 수 있을 것 같다. 물론 형 변환이 많고 역순으로 돌려야하는 과정이 필요하기 때문에 수행 시간은 보장 못하지만 구현은 쉬워보인다.

이 방식으로 코드를 작성하기 위해서는 연결 리스트를 역순으로 만드는 함수, 연결 리스트를 리스트로 변환하는 함수, 리스트를 연결 리스트로 변환하는 함수가 필요하다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev
    def toList(self, node: ListNode) -> List:
        list:List = []
        while node:
            list.append(node.val)
            node = node.next
        return list
    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))
        resultStr = int(''.join(str(e) for e in a)) + int(''.join(str(e) for e in b))
        return self.toReversedLinkedList(str(resultStr))

수행 시간이 길거나 이상한 부분은 없었지만 문제에서 의도한 코드가 아님은 확실해보인다.

Solution 2 전가산기 구현

논리 회로의 전가산기와 유사한 형태로 구현해볼 것이다. 이진법이 아니라 십진법을 사용한다는 점이 다르긴 하지만 자리 올림수를 구하는 것까지 가산기의 원리와 거의 일치한다. 두 연결 리스트의 각 노드 값을 더한 값을 divmod()를 통해 자리 올림수와 사용될 수를 구하여서 자리 올림을 구현한다. divmod()의 첫번째 인자는 sum+carry(이전의 자리 올림수)이고 두번째 인자는 10이다. 10//sum+carry가 1이라면 1을 올림처리 하게 되는 것이다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        root = head = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            sum=0
            if l1:
                sum+=l1.val
                l1=l1.next
            if l2:
                sum+=l2.val
                l2=l2.next
            carry, val = divmod(sum+carry, 10)
            head.next = ListNode(val)
            head = head.next
        return root.next

solution 1에 비해 훨씬 깔끔한 코드가 완성되었다. 성능 또한 비슷하다.

문법: 숫자형 리스트를 단일 값으로 병합하기

Solution 1에서는 숫자형 리스트를 문자형으로 변환하고 숫자형으로 다시 변환하는 불필요한 작업을 진행했다. 이와 같은 코드는 좋은 코드가 아니다.

>>> ''.join(str(e) for e in a)
'12345'

이 코드는 가독성이 떨어지고 보기 좋지 않다. 더 깔끔한 방법이 있다.

>>> ''.join(map(str, a))
'12345'

이 경우 임시 변수 e를 사용하지 않아 깔끔하며 map(str, 로 이어지는 부분이 문자열로 변환함을 암시하는 뉘앙스를 주기 때문에 가독성도 좋다. 코드의 크기 또한 줄어들었다. 그러나 우아함과는 거리가 조금 있는 코드이다. 숫자형을 바로 변환하는 방법이 있다.

>>> functool.reduce(lambda x, y: 10 * x + y, a, 0)
12345

functool은 함수를 다루는 함수라는 뜻으로 고계 함수를 지원하는 함수형 언어 모듈이다. 여기서 reduce는 두 인수의 함수를 누적 적용하라는 메소드이다.

>>> functool.reduce(lambda x, y: x + y, [1, 2, 3, 4, 5])
15

위의 코드는 x + y라는 식을 [1, 2, 3, 4, 5]라는 배열로 실행하라는 의미가 된다.

좀 더 가독성을 높이는 방법으로 operator 모듈을 활용하는 방법이 있다. 이 경우 연산자의 명칭을 reduce의 인자로 줄 수 있기 때문에 가독성이 매우 좋다. 또한 고계 함수이기 때문에 파라미터를 함수로 넘기는 것도 가능하다.

>>> from operator import add, mul
>>> functool.reduce(add, [1, 2, 3, 4, 5])
15
>>> functool.reduce(mul, [1, 2, 3, 4, 5])
120

LeetCode 24.Swap Nodes in Pairs

연결 리스트를 입력받아 페어 단위로 스왑하라.

Solution 1 값만 교환

직관적인 방법으로 연결 리스트의 노드를 변경하는 것이 아니라 노드 구조는 그대로 유지하고 값만 변경하는 방법이다. 이 방식은 실용성과는 거리가 매우 멀다. 보통 연결 리스트는 복잡한 여러가지 값들의 구조체로 구성되어 있고 사실상 값만 바꾸는 것은 매우 어려운 일이나, 이 문제의 경우 단 하나의 값으로 구성된 단순한 연결 리스트이기 때문에 값을 바꾸는 정도는 어렵지 않다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node = head 
        while node and node.next:
            node.val, node.next.val = node.next.val, node.val
            node = node.next.next
        return head

이 방법은 빨리 풀기 위해서 코딩 테스트에서 사용하기에는 매우 좋지만 코드 리뷰에서 좋지 않은 피드백을 받을 가능성이 있다. 그럴 경우에는 빨리 풀기 위해 시도한 방법임을 알리고 다음 풀이인 Solution 2 풀이법에 대해 설명할 수 있어야 한다.

Solution 2 반복 구조로 스왑

단순히 값을 바꾸는 것에 비해 연결 리스트의 구조를 바꾸는 것은 생각보다 복잡하다. 1->2->3->4->5->6이라는 연결 리스트가 있을 경우에 3->4를 4->3으로 바꾸면 그 앞인 2가 가리키는 연결 리스트와 5로 연결되는 연결 리스트도 모두 변경해야 한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root = prev = ListNode(None)
        prev.next = head
        while head and head.next:
            b = head.next
            head.next = b.next
            b.next = head
            prev.next = b
            head = head.next
            prev = prev.next.next
        return root.next

이전 풀이와 다르게 연결 리스트의 head를 가리키는 노드가 직접 바뀌는 풀이이기 때문에 head를 반환하지 못하고 그 이전 값을 root로 지정하여 root.next를 반환하도록 했다.

Solution 3 재귀 구조로 스왑

재귀로는 훨씬 더 깔끔하게 풀이할 수 있다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head and head.next:
            p = head.next
            head.next = self.swapPairs(p.next)
            p.next = head
            return p
        return head

반복 풀이와 달리 포인터 역할을 하는 p 변수 하나만 있으면 충분히 구현이 가능하다. 더미 노드를 만들 필요 없이 바로 head를 반환하기 때문에 공간 복잡도가 낮다. p는 head.next가 되고 p.next는 head가 된다. 이 사이에 재귀 호출로 게속 스왑된 값을 반환받는다. 실제로는 백트래킹이 되면서 연결 리스트가 이어진다. 이러한 재귀 풀이 방식은 불필요한 변수의 사용을 줄여 공간 복잡도를 낮추고 빈틈없는 코드 구조를 지녀 짜임새 있다는 느낌이 든다. 바로 좋은 코드의 예이다.

LeetCode 328.Odd Even Linked List

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

Solution 1 반복 구조로 홀짝 노드 처리

공간 복잡도와 시간 복잡도 제약 사항이 있기 때문에 쉽게 생각해서는 안되는 문제이다. 제약이 없을 경우 연결 리스트를 리스트로 변환하여 슬라이싱과 같은 다양한 함수를 사용해 쉽고 직관적으로 풀 수 있지만 이러한 방식은 우아하지 않다. 오프라인 코딩 테스트의 경우 이러한 편법을 이용하면 면접관이 다시 풀어달라고 하는 경우도 있다.

홀수 노드 다음에 짝수 노드가 오기 위해서 홀짝 각 노드를 구성한 후 홀수 노드의 마지막을 짝수 노드의 처음과 연결하면 될 것 같다.

odd.next, even.next = odd.next.next, even.next.next
odd, even = odd.next, even.next

이 코드를 이용해서 홀짝을 구성하고

odd.next = even_head

이 코드를 이용해 홀 뒤에 짝이 붙도록 연결한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        odd = head
        even = head.next
        even_head = head.next
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
        odd.next = even_head
        return head

LeetCode 92.Reverse Linked List 2

인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

Solution 1 반복 구조로 노드 뒤집기

1->2->3->4->5->6 연결 리스트와 m=2, n=5가 주어진다고 가정하고 풀어보자.

root = start = ListNode(None)
root.next = head
for _ in range(m-1):
    start = start.next
end = start.next

start는 변경이 필요한 2의 바로 앞 지점인 1을 가리키게 하고 end는 start.next인 2를 가리키게 한다. head는 1이고, head앞에 존재하는 root를 만든다. 마지막에 root.next를 반환할 예정이다.

위의 그림과 같은 과정을 거치게 된다. 2)부터가 반복이 진행되는 부분으로 start.next는 end.next가 된다. end.next는 end.next.next가 되고, start.next.next를 tmp로 지정한다. 즉 이전에 start.next였던 노드를 배치하는 것과 동일하다. 이 과정에서 start 노드와 end 노드는 변하지 않는다. 다만 연결이 바뀔 뿐이다.

for _ in range(n-m):
    tmp, start.next, end.next = start.next, end.next, end.next.next
    start.next.next = tmp

위의 코드로 그림의 과정을 나타낼 수 있다. 위의 코드를 다중할당 하지 않고 나타내면 다음과 같다.

for _ in range(n-m): # 2)의 경우
    tmp = start.next # 2를 tmp에 저장
    start.next = end.next # 1이 3을 가리키게함.
    end.next = end.next.next # 2가 4를 가리키게함.
    start.next.next = tmp # 3이 2를 가리키게함

2) 과정을 예로 주석을 달아보았다. 코드를 실제로 작성할 때에는 다중 할당을 이용해 간결하게 작성하는 것이 좋다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
        if not head or m==n:
            return head
        root = start = ListNode(None)
        root.next = head
        for _ in range(m-1):
            start = start.next
        end = start.next
        for _ in range(n-m):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp
        return root.next

이렇게 연결 리스트에 대해 공부해보았다. 연결 리스트는 예전에 제대로 해놓지 않아서 조금은 헷갈리는 것 같다. 연결 리스트 문제를 찾아서 더 풀어보는 연습 시간을 가지자!