Plus One

Q: Plus One의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 n 개의 숫자에 대해 O(n) 시간이 걸립니다. 모든 숫자가 9인 경우 모든 숫자를 처리하기 때문입니다. 조기 종료 버전은 뒤에서부터 이어지는 9들을 처리한 뒤 멈추며, 결과에 맨 앞에 새 숫자가 필요한 경우를 제외하면 추가 공간으로 O(1) 을 사용합니다.

쉬움수학과 시뮬레이션

+10

음이 아닌 정수는 십진수 각 자릿수를 담은 배열 digits로 저장되며, 가장 큰 자릿수가 앞에 옵니다. 472는 [4, 7, 2]입니다. 숫자에 1을 더하고, 결과의 자릿수를 같은 형식으로 반환하세요. 숫자는 최대 100자리일 수 있으며, 이는 64비트 정수가 담을 수 있는 범위보다 훨씬 큽니다.

함수

plusOne(digits: integer-array) → integer-array

digitsinteger-array: 숫자의 자릿수를 최상위 자리부터
반환값integer-array: 숫자의 각 자릿수를 더한 값에 1을 더한 것으로, 가장 높은 자릿수부터 나열합니다

제약 조건

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits에는 선행 0이 없으며, 숫자 0 자체인 경우만 예외로 [0]입니다.

예제

입력: digits = [4, 3, 9]
출력: [4, 4, 0]
설명: 숫자는 439이고, 439 + 1 = 440입니다. 마지막 숫자 9는 0으로 바뀌고 올림수를 3에 전달하여 3이 4가 됩니다.

입력: digits = [0]
출력: [1]
설명: 숫자 0은 [0]으로 쓰며, 0 + 1 = 1입니다.

후속 질문

대신 1을 빼려면 어떻게 해야 할까요? 숫자가 1 이상일 때요. 결과에서 앞자리 숫자가 사라지는 경우는 언제일까요? 예를 들어 [1, 0, 0]처럼요?

풀이

100자리 수는 약 1.8 × 10^19에서 한계에 도달하는 모든 64비트 정수의 범위를 초과하므로, 변환해서 더할 수 없습니다. 종이에 계산할 때처럼 마지막 자리부터 받아올림을 하며 더하세요. 1을 더하면 뒤에 연속된 9들만 바뀌어 0이 되고, 그 왼쪽 자릿수도 바뀝니다.

올림을 하며 자릿수별로 더하기

핵심 아이디어

더하려는 값인 1을 올림값으로 시작하세요. 오른쪽부터 각 자릿수에서 열의 합은 해당 자릿수와 올림값을 더한 값입니다. total % 10은 답에 들어가고, total / 10은 다음 올림값이 됩니다. 합은 최대 9 + 1 = 10이므로 올림값은 0 또는 1입니다. 첫 번째 자릿수를 처리한 뒤에도 올림값이 남아 있으면 999 + 1 = 1000의 경우처럼 맨 앞에 새로운 자릿수가 됩니다.

답을 마지막 자릿수부터 만들게 되므로, 그 순서대로 모은 다음 끝에서 뒤집으세요. 시간 복잡도는 O(n)이고 최대 n + 1개의 자릿수를 담는 새 배열이 필요합니다.

알고리즘

carry를 1로 설정하고 정답을 담을 빈 목록을 시작합니다.
마지막 숫자부터 첫 번째 숫자까지 각각에 대해 total = digit + carry를 계산합니다.
total % 10을 정답에 추가하고 carry를 total / 10으로 설정한 다음, 소수점 이하를 버립니다.
반복문이 끝난 후 carry가 1이면 이를 추가합니다.
정답을 뒤집고 반환합니다.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

9보다 작은 첫 번째 숫자에서 멈추기

핵심 아이디어

9보다 작은 숫자는 올림값 1을 흡수합니다. 즉, 값이 1 증가하고 왼쪽에 있는 모든 숫자는 그대로 유지됩니다. 9만 0으로 바뀌면서 올림값을 넘깁니다. 따라서 처음으로 9보다 작은 숫자에서 멈추고 제자리에서 변경된 입력 배열을 반환하면 됩니다. [2, 9, 0, 9]의 경우 마지막 9는 0이 되고, 0은 1이 되므로 처음 두 숫자를 읽지 않고도 [2, 9, 1, 0]을 반환합니다.

9보다 작은 숫자가 없다면, 그 수는 10^n - 1이며 답은 1 뒤에 n개의 0이 오는 형태입니다. 이 경우에만 새 배열이 필요하므로, 그 외의 경우 추가 공간은 O(1)입니다.

알고리즘

인덱스를 마지막부터 처음까지 순회합니다.
숫자가 9보다 작으면 1을 더하고 배열을 반환합니다.
그렇지 않으면 숫자는 9입니다. 숫자를 0으로 설정하고 왼쪽으로 한 자리 이동합니다.
루프가 끝나면 모든 숫자가 9였던 것입니다. 1 뒤에 n개의 0이 오는 값을 반환합니다.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

함정과 경계 사례

배열을 정수로 변환했다가 다시 되돌리는 것. 64비트 정수는 최대 19자리 또는 20자리만 저장할 수 있으므로 100자리는 오버플로되고, 부동 소수점 수는 그보다 더 일찍 마지막 자릿수를 잃습니다.
올림으로 생기는 추가 자릿수를 잊는 것. [9, 9, 9]는 [1, 0, 0, 0]이 되어야 합니다. 기존 자릿수만 다시 쓰는 코드는 [0, 0, 0]을 반환합니다.
첫 번째 자릿수에 1을 더하는 것. 배열은 최상위 자릿수가 먼저 오므로 일의 자릿수는 마지막 요소입니다.
9보다 작은 자릿수가 올림값을 받아들였을 때 반환하지 않는 것. 그러면 루프가 그대로 유지되어야 하는 자릿수까지 변경합니다. [1, 9, 3]은 [1, 9, 4]가 되어야 합니다.
Lua와 R에서는 배열이 1부터 시작하므로 마지막 자릿수의 인덱스는 n - 1이 아니라 n입니다.

자주 묻는 질문3

Plus One의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 n개의 숫자에 대해 O(n) 시간이 걸립니다. 모든 숫자가 9인 경우 모든 숫자를 처리하기 때문입니다. 조기 종료 버전은 뒤에서부터 이어지는 9들을 처리한 뒤 멈추며, 결과에 맨 앞에 새 숫자가 필요한 경우를 제외하면 추가 공간으로 O(1)을 사용합니다.

숫자를 정수로 변환하지 않는 이유는 무엇인가요?

숫자는 100자리일 수 있지만, 64비트 정수는 약 1.8 × 10^19, 즉 20자리에서 한계에 도달합니다. Python과 Ruby는 무제한 정수를 지원하므로 변환이 가능하지만, 이 코드는 다른 언어에서는 그대로 사용할 수 없습니다. 숫자를 한 자리씩 처리하면 오버플로가 발생하지 않습니다.

숫자 배열로 저장된 두 숫자를 어떻게 더하나요?

각 배열의 끝에 있는 인덱스를 하나씩 사용해 열 방식으로 계산하세요. 각 열에서는 없는 숫자를 0으로 간주하고 올림수를 더해 두 숫자를 더합니다. 두 배열의 숫자를 모두 사용하고 올림수가 0이 되면 멈춘 다음, 모은 숫자들을 뒤집으세요.

def plusOne(digits):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

digits = [4, 3, 9]

예상 출력

[4, 4, 0]