Add Two Numbers

Q: 연결 리스트로 저장된 두 수를 더하는 시간 복잡도는 얼마인가요?

O(max(L1, L2)) 입니다. 열마다 한 단계씩 수행하고, 끝에 올림수가 남으면 한 단계 더 수행합니다. 결과를 제외하면 단일 패스 버전은 O(1) 메모리를 사용합니다. 두 개의 포인터와 올림수만 필요합니다.

보통연결 리스트 수학과 시뮬레이션

+10

음수가 아닌 두 정수가 주어지며, 각 정수는 가장 낮은 자릿수부터 저장된 단일 연결 리스트로 표현됩니다. 첫 번째 리스트에서 노드 i는 숫자 values1[i]를 담고 노드 next1[i]에 연결됩니다. 두 번째 리스트도 next2와 values2를 사용해 같은 방식으로 구성됩니다. 두 리스트 모두 -1은 리스트의 끝을 나타내며 헤드는 노드 0입니다. 노드는 리스트 순서대로 저장되어 있지 않으므로 연결을 따라가세요.

두 수의 합을 가장 낮은 자릿수부터 나타내는 숫자들을 반환하세요.

함수

addTwoNumbers(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: 첫 번째 숫자의 각 노드가 연결되는 노드의 인덱스 또는 마지막 노드의 경우 -1
values1integer-array: 첫 번째 숫자의 각 노드가 보유한 숫자
next2integer-array: 두 번째 숫자의 각 노드가 연결되는 노드의 인덱스 또는 마지막 노드의 경우 -1
values2integer-array: 두 번째 숫자의 각 노드가 담고 있는 숫자
반환값integer-array: 합계의 자릿수, 가장 낮은 자리부터

제약 조건

1 ≤ L1 ≤ 100이며, 여기서 L1은 next1과 values1의 길이입니다.
1 ≤ L2 ≤ 100이며, 여기서 L2는 next2와 values2의 길이입니다.
0 ≤ values1[i], values2[j] ≤ 9
next1의 각 항목은 -1이거나 첫 번째 리스트의 노드 인덱스이며, next2의 각 항목은 -1이거나 두 번째 리스트의 노드 인덱스입니다.
노드 0에서 시작하여 각 리스트는 모든 노드를 정확히 한 번 방문한 다음 -1에 도달합니다. 순환은 없습니다.
어떤 숫자에도 앞에 0이 붙지 않습니다. 목록의 마지막 노드에는 0이 아닌 숫자가 들어 있습니다. 단, 목록이 한 자리 숫자인 0인 경우는 예외입니다.

예제

입력: next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
출력: [5, 4, 1, 1]
설명: 첫 번째 리스트는 노드 0, 2, 1을 방문하고 8, 1, 6을 읽어 숫자 618을 만듭니다. 두 번째 리스트는 7, 2, 5를 읽어 숫자 527을 만듭니다. 두 수의 합은 1145이므로 답은 5, 4, 1, 1입니다.

입력: next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
출력: [0, 0, 0, 0, 1]
설명: 두 번째 목록은 1, 9, 9, 9, 즉 숫자 9991을 나타냅니다. 9를 더하면 10000이 됩니다. 각 자릿수에서 0이 나오고 올림이 발생하며, 마지막 올림은 다섯 번째 자릿수가 됩니다.

입력: next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
출력: [7, 5]
설명: 첫 번째 숫자는 0이고 두 번째 목록은 숫자 57을 나타내는 7, 5입니다. 0을 더해도 아무것도 바뀌지 않으므로 답은 [7, 5]입니다.

후속 질문

목록에 최상위 자릿수가 먼저 저장되어 있다면 숫자를 어떻게 더할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

숫자가 너무 커서 어떤 정수형에도 담을 수 없으므로, 종이에 쓸 때처럼 열마다 더하고 열의 합이 10에 도달하면 1을 올림합니다. 리스트는 일의 자리부터 저장하므로, 리스트를 순회하면 더하는 순서대로 각 자리를 방문하게 됩니다.

숫자를 옮겨 적은 다음, 열별로 더하세요

핵심 아이디어

여기서 포인터는 노드 인덱스이며, 다음으로 이동하는 것은 node = next[node]입니다. 각 연결 리스트의 숫자를 배열에 복사하여 인덱스 i에 10^i의 자릿값을 갖는 숫자를 저장합니다. 첫 번째 예에서는 [8, 1, 6]과 [7, 2, 5]입니다.

그런 다음 종이에 덧셈을 하듯이 더하되, 없는 숫자는 0으로 셉니다. 각 자릿수에서 sum % 10을 기록하고 나머지는 올림합니다. 8 + 7 = 15에서는 5를 기록하고 1을 올림하며, 1 + 2 + 1 = 4이고, 6 + 5 = 11에서는 1을 기록합니다. 마지막 올림은 최종 숫자가 됩니다. [5, 4, 1, 1].

복사에는 덧셈에는 전혀 필요하지 않은 추가 메모리 O(L1 + L2)가 듭니다.

알고리즘

각 리스트를 노드 0부터 순회하며 숫자를 배열에 복사합니다.
carry = 0으로 설정합니다. 더 긴 배열의 길이까지 각 인덱스 i에 대해, 존재하는 i 위치의 숫자와 올림수를 더합니다.
sum % 10을 추가하고 carry를 내림한 sum / 10으로 설정합니다.
마지막 자릿수 이후에도 올림수가 1이면 이를 추가합니다.

def readDigits(next, values):
    # The digits in list order: least significant first.
    digits = []
    node = 0
    while node != -1:
        digits.append(values[node])
        node = next[node]
    return digits


def addTwoNumbers(next1, values1, next2, values2):
    first = readDigits(next1, values1)
    second = readDigits(next2, values2)
    result = []
    carry = 0
    for i in range(max(len(first), len(second))):
        column = carry
        if i < len(first):
            column += first[i]
        if i < len(second):
            column += second[i]
        result.append(column % 10)
        carry = column // 10
    if carry > 0:
        result.append(carry)
    return result

올림수를 유지하면서 두 목록을 동시에 살펴보세요

핵심 아이디어

열 i에서는 각 리스트의 i번째 노드만 사용하므로, 각 리스트마다 포인터 하나씩(a와 b)을 두고 열이 진행될 때 둘 다 이동합니다.

하나의 루프는 a가 -1이 아니거나, b가 -1이 아니거나, 올림수가 1인 동안 실행됩니다. 아직 노드가 있는 포인터는 해당 자릿수를 더하고 다음으로 이동하며, -1을 가리키는 포인터는 아무것도 더하지 않습니다. 이렇게 하면 두 번째 루프 없이 길이가 다른 숫자도 처리할 수 있고, 올림수 조건에 따라 끝에 추가 자릿수를 기록합니다.

두 번째 예시인 9 더하기 9991에서는 모든 열의 합이 10이 되어 0을 기록합니다. 네 개의 열을 처리한 후 두 리스트는 모두 끝나지만 올림수가 1이므로 루프가 한 번 더 실행됩니다. 결과는 [0, 0, 0, 0, 1]입니다. 답 외에 정수 세 개를 유지합니다.

알고리즘

a = 0, b = 0, carry = 0으로 설정합니다.
a != -1 또는 b != -1 또는 carry > 0인 동안, 열의 합을 carry로 시작합니다.
a != -1이면 values1[a]를 더하고 a = next1[a]로 설정합니다. 두 번째 목록의 b에 대해서도 똑같이 합니다.
sum % 10을 추가하고 carry를 내림한 sum / 10으로 설정합니다.
추가한 숫자들을 반환합니다.

def addTwoNumbers(next1, values1, next2, values2):
    a = 0  # current node of the first number
    b = 0  # current node of the second number
    carry = 0
    result = []
    # Keep going while either number has digits left or a carry is waiting.
    while a != -1 or b != -1 or carry > 0:
        column = carry
        if a != -1:
            column += values1[a]
            a = next1[a]
        if b != -1:
            column += values2[b]
            b = next2[b]
        result.append(column % 10)  # the digit this column writes
        carry = column // 10  # 1 when the column reached 10, else 0
    return result

함정과 경계 사례

각 리스트를 정수로 변환해 더하기. 100자리 숫자는 모든 64비트 자료형의 범위를 넘습니다.
마지막 올림수를 버리기. 두 리스트가 모두 끝나면 멈추는 루프는 두 번째 예제에서 [0, 0, 0, 0]을 반환합니다.
더 짧은 리스트가 끝나면 멈추기. 그러면 두 번째 예제에서 9991의 9 세 개와 그 사이로 이어지는 올림수를 놓치게 됩니다.
배열 순서대로 숫자를 읽기. 첫 번째 예제에서 values1은 [8, 6, 1]이지만, 링크를 따라 읽으면 숫자는 618입니다.
배열이 1부터 시작하는 Lua와 R에서 오프셋을 잊지 않기. 노드 ID는 0부터 시작하도록 유지하고 next1[node + 1]을 읽으세요.

자주 묻는 질문3

두 숫자 더하기에서 숫자들이 거꾸로 저장되는 이유는 무엇인가요?

덧셈은 일의 자리부터 시작하며, 단일 연결 리스트는 머리에서부터만 순회할 수 있습니다. 최하위 자릿수가 먼저 오면 순회 순서가 덧셈을 수행하는 열의 순서와 같으므로, 올림값은 포인터를 따라 앞으로 이동합니다.

연결 리스트로 저장된 두 수를 더하는 시간 복잡도는 얼마인가요?

O(max(L1, L2))입니다. 열마다 한 단계씩 수행하고, 끝에 올림수가 남으면 한 단계 더 수행합니다. 결과를 제외하면 단일 패스 버전은 O(1) 메모리를 사용합니다. 두 개의 포인터와 올림수만 필요합니다.

올림값이 1보다 클 수 있나요?

아니요. 한 열에서는 최대 9인 두 자리와 최대 1인 올림수를 더하므로 합은 최대 19입니다. 10으로 나누고 내림하면 0 또는 1이 됩니다.

def addTwoNumbers(next1, values1, next2, values2):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

next1 = [2, -1, 1]
values1 = [8, 6, 1]
next2 = [2, -1, 1]
values2 = [7, 5, 2]

예상 출력

[5, 4, 1, 1]