파이썬으로 이진수 연결 리스트를 십진 정수로 변환하는 방법

단일 연결 리스트(singly linked list)가 하나 주어져 있고, 이 리스트는 최상위 비트(MSB)부터 순서대로 이진수를 표현하고 있다고 가정해 보겠습니다. 우리가 해야 할 일은 이 연결 리스트를 읽어 들여 해당하는 십진 정수로 변환하여 반환하는 것입니다.

문제 이해하기

예를 들어 입력이 [1, 0, 1, 1, 0]이라면, 이는 이진수 10110을 의미합니다. 이를 십진수로 바꾸면 다음과 같습니다.

1×2⁴ + 0×2³ + 1×2² + 1×2¹ + 0×2⁰ = 16 + 0 + 4 + 2 + 0 = 22

따라서 출력값은 22가 됩니다.

풀이 접근 방법

이 문제는 다음 단계를 거쳐 해결할 수 있습니다.

• 값들을 담을 새로운 리스트 l을 생성합니다.
• 노드가 null이 아닌 동안 반복하면서 각 노드의 값을 l의 끝에 차례로 추가하고, 노드를 다음 노드로 이동시킵니다.
• 자릿수 지수를 나타낼 k = 0, 결과값을 저장할 v = 0으로 초기화합니다.
• 리스트의 마지막 원소(최하위 비트)부터 첫 번째 원소(최상위 비트)까지 역순으로 순회하면서, 값이 1인 자리마다 v에 2^k를 더하고 매번 k를 1씩 증가시킵니다.
• 최종적으로 누적된 v를 반환합니다.

구현 예제

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

class Solution:
    def solve(self, node):
        l = []
        while node:
            l.append(node.val)
            node = node.next
        k = 0
        v = 0
        for i in range(len(l) - 1, -1, -1):
            if l[i] == 1:
                v += (2 ** k)
            k += 1
        return v

ob = Solution()
head = make_list([1, 0, 1, 1, 0])
print(ob.solve(head))

입력

[1, 0, 1, 1, 0]

출력

22

동작 원리 살펴보기

연결 리스트를 순회하며 모든 값을 일반 파이썬 리스트에 옮긴 뒤, 뒤에서부터 앞으로 스캔하면서 각 자리의 가중치(2의 거듭제곱)를 곱해 더하는 방식입니다. 시간 복잡도는 리스트를 두 번 순회하므로 O(n)이며, 공간 복잡도 역시 값을 저장하는 리스트 때문에 O(n)입니다.

참고로 공간을 더 아끼고 싶다면 리스트에 값을 따로 저장하지 않고, 순회하면서 result = result * 2 + node.val 공식을 적용하는 방법도 있습니다. 이 경우 공간 복잡도를 O(1)로 줄일 수 있습니다.