Plus One
음수가 아닌 정수는 십진수 자릿수의 배열인 digits에 가장 높은 자릿수부터 저장됩니다. 예를 들어 472는 [4, 7, 2]입니다. 이 수에 1을 더하고, 결과의 자릿수를 같은 형식으로 반환하세요. 이 수는 최대 100자리까지일 수 있으며, 이는 64비트 정수에 저장할 수 있는 자릿수보다 훨씬 많습니다.
함수
- digitsinteger-array
- 숫자의 각 자릿수를 가장 높은 자리부터
- 반환값integer-array
- 숫자의 자릿수를 가장 높은 자리부터 하나씩 더한 값
제약 조건
1 ≤ digits.length ≤ 1000 ≤ digits[i] ≤ 9digits에는 선행 0이 없습니다. 단, 숫자 0 자체는[0]입니다.
예제
- 입력
- digits = [4, 3, 9]
- 출력
- [4, 4, 0]
- 설명
- 숫자는 439이고, 439 + 1 = 440입니다. 마지막 숫자 9가 0으로 바뀌고 올림수를 3에 전달하여 3이 4가 됩니다.
- 입력
- digits = [9, 9]
- 출력
- [1, 0, 0]
- 설명
- 99 + 1 = 100. 두 9는 모두 0으로 바뀌고, 남은 올림수가 새로운 맨 앞자리 숫자가 되므로 답은 입력보다 한 자리 더 깁니다.
- 입력
- digits = [0]
- 출력
- [1]
- 설명
- 숫자 0은
[0]으로 쓰며, 0 + 1 = 1입니다.
제출 시 숨은 테스트 +13개
후속 질문
대신 최소 1인 수에서 1을 빼려면 어떻게 해야 할까요? 어떤 자릿수가 바뀌며, [1, 0, 0]에서처럼 결과에서 맨 앞 자릿수가 사라지는 경우는 언제일까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
숫자는 100자리일 수도 있어 내장 정수형으로는 처리하기에 너무 큽니다. 종이에 덧셈을 하듯이 각 자릿수를 더하세요. 1은 처음에 어디로 가나요?
9보다 작은 숫자에 1을 더하면 올림이 발생하지 않으므로 왼쪽의 숫자는 바뀌지 않습니다. 9만 0으로 바뀌고 올림을 다음 자리로 넘깁니다.
마지막 숫자부터 왼쪽으로 이동합니다. 각 9를 0으로 바꾸고, 9보다 작은 숫자가 처음 나오면 1을 더한 뒤 반환합니다. 그런 숫자를 찾지 못했다면 모든 숫자가 9였다는 뜻입니다. 답은 1 뒤에 0이 이어지는 형태입니다.
풀이
숫자들을 하나의 수로 변환하고 1을 더한 뒤 다시 변환하는 방법은 여기서 실패합니다. 100자리 숫자는 64비트 정수의 범위를 초과하며, 64비트 정수는 약 1.8 × 10^19에서 한계에 도달합니다. 따라서 종이에 계산하듯 마지막 자리부터 올림수를 적용해 더합니다. 작업을 줄여 주는 한 가지 관찰이 있습니다. 1을 더하면 끝에 연속된 9들만 바뀌어 0이 되고, 그 왼쪽의 첫 번째 숫자도 바뀝니다. 나머지 숫자는 모두 그대로입니다.
자리올림을 하며 한 자리씩 더하기
핵심 아이디어
학교에서 하듯이 숫자를 적고 마지막 자릿수 아래에 1을 더하세요. 더하려는 수인 1을 올림수로 시작하세요. 오른쪽에서부터 각 자릿수마다 열의 합은 해당 자릿수와 올림수를 더한 값입니다. 그 값의 마지막 자릿수인 total % 10은 답에 넣고, 십의 자릿수인 total / 10은 다음 열의 올림수가 됩니다.
올림수가 1이면 열의 합은 최대 9 + 1 = 10이므로 올림수는 항상 0 또는 1입니다. 첫 번째 자릿수를 처리한 뒤에도 올림수가 남아 있으면 답에 새로운 앞자리 숫자가 추가됩니다. 999 + 1을 계산하려면 1000의 1을 적을 네 번째 자리가 필요합니다.
답은 계산하는 순서 때문에 마지막 자릿수부터 만들어집니다. 그 순서대로 모은 다음 마지막에 뒤집으세요. 이 방법은 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 result9보다 작은 첫 번째 숫자에서 멈추세요
핵심 아이디어
정확히 1을 더할 때 올림이 어떻게 처리되는지 살펴보세요. 9보다 작은 숫자는 올림을 흡수합니다. 3은 4가 되고 올림은 0이 되며, 그보다 왼쪽에 있는 모든 숫자는 값이 그대로 유지됩니다. 9만 0으로 바뀌면서 올림을 넘깁니다. 따라서 1을 더한다는 것은 끝에 이어진 9들을 0으로 바꾼 다음, 그 앞의 숫자에 1을 더하는 것입니다.
마지막 숫자부터 왼쪽으로 이동하세요. 9를 만나면 0을 쓰고 계속 진행합니다. 다른 숫자를 만나면 그 숫자를 1 증가시키고 바로 배열을 반환하세요. 그보다 왼쪽에 있는 숫자들은 바뀔 수 없기 때문입니다. [2, 9, 0, 9]의 경우 마지막 9가 0이 되고, 0은 1이 되며, 처음 두 숫자는 확인하지 않고 [2, 9, 1, 0]에서 멈춥니다.
반복문에서 9보다 작은 숫자를 찾지 못하면 모든 숫자가 9였으며 이제 0이 된 것입니다. 이 숫자는 10^n - 1이었으므로, 정답은 1 뒤에 n개의 0이 이어지는 수입니다. 새 배열이 필요한 경우는 이것뿐입니다. 그 외에는 입력을 제자리에서 변경하므로 추가 공간은 O(1)이고, 반복문은 끝에 이어진 9의 개수에 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
함정과 경계 사례
주의할 점은 정수 오버플로와 모든 숫자가 9인 경우입니다.
- 배열을 정수로 바꿨다가 다시 배열로 변환하기. 작은 테스트는 통과하지만 100자리 숫자에서는 실패합니다. 64비트 정수는 최대 19~20자리까지만 담을 수 있고, 부동소수점 숫자는 그보다 더 일찍 마지막 자릿수를 잃습니다.
- 자릿수가 하나 더 늘어나는 경우를 잊기.
[9, 9, 9]는 네 자리인[1, 0, 0, 0]이 되어야 합니다. 기존 자릿수만 다시 쓰는 코드는[0, 0, 0]을 반환합니다. - 마지막 숫자 대신 첫 번째 숫자에 1을 더하기. 배열은 가장 큰 자릿수가 먼저 오므로 일의 자리는 끝에 있습니다.
- 9보다 작은 숫자가 올림을 흡수한 뒤 반환하는 것을 잊기. 조기 종료 버전에서는 반복문이 계속 진행되어 그대로 유지해야 하는 숫자까지 바뀝니다.
[1, 9, 3]에서는 3만 바뀌어야 하므로 정답은[1, 9, 4]입니다. - 배열 인덱스가 1부터 시작하는 Lua와 R에서 인덱스 순서를 혼동하기. 마지막 숫자는 인덱스
n에 있고, 새로운 맨 앞의 1은 인덱스 1 앞에 들어갑니다.
자주 묻는 질문4
Plus One의 시간 복잡도는 얼마인가요?
두 접근 방식 모두 n개의 숫자에 대해 O(n) 시간이 걸립니다. 최악의 경우인 모든 숫자가 9인 경우에는 모든 숫자를 확인하기 때문입니다. 조기 종료 버전은 뒤에서부터 이어지는 9 다음에 멈추므로, 9보다 작은 숫자로 끝나는 수에서는 한 단계만 수행합니다. 답에 새로운 앞자리 숫자가 필요한 경우를 제외하면 추가 공간은 O(1)입니다.
숫자들을 정수로 변환하면 안 되나요?
숫자는 100자리일 수 있고 64비트 정수는 약 1.8 × 10^19, 즉 20자리에서 한계에 도달하기 때문입니다. Python과 Ruby는 정수의 크기에 제한이 없으므로 그 언어에서는 변환이 가능하지만, 그러면 연습의 요점을 놓치게 되고 다른 언어에는 그대로 적용되지 않습니다. 자릿수별로 처리하면 오버플로가 발생하지 않습니다.
결과의 자릿수가 입력보다 많아지는 경우는 언제인가요?
모든 숫자가 9일 때만 해당합니다. 그러면 그 수는 10^n - 1이고, 여기에 1을 더하면 10^n이 됩니다. 즉, 1 뒤에 n개의 0이 오는 수입니다. 숫자 중 하나라도 9보다 작으면 올림값을 흡수하므로 자릿수는 그대로 유지됩니다.
숫자 배열로 저장된 두 수를 어떻게 더하나요?
첫 번째 접근 방식의 열 계산법을 사용하고, 두 배열의 끝에 인덱스를 하나씩 둡니다. 각 열에서는 숫자 두 개를 더하고, 없는 숫자는 0으로 취급하며 올림수도 더합니다. 두 배열의 숫자를 모두 사용하고 올림수가 0이 될 때까지 계속한 다음, 모은 숫자들을 뒤집습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def plusOne(digits):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
digits = [4, 3, 9]
기대값
[4, 4, 0]