정수 리스트 n이 하나 주어져 있다고 가정해 봅시다. 이 리스트는 하나의 십진수를 나타내며, 각 원소 n[i]는 0부터 9 사이의 값을 가집니다. 예를 들어 n이 [2, 4, 9]라면 이는 숫자 249를 의미합니다.
우리가 해야 할 일은 이 숫자에 1을 더한 결과를 동일한 리스트 형태로 반환하는 것입니다.
문제 예시
입력이 n = [9, 9]라면, 99에 1을 더하면 100이 되므로 출력은 [1, 0, 0]이 됩니다. 이처럼 마지막 자릿수가 9일 경우 올림(carry)이 연쇄적으로 발생할 수 있어 단순히 마지막 원소만 바꾸는 것으로는 해결되지 않습니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 리스트 맨 앞에 0을 추가합니다. 최고 자릿수의 올림으로 자릿수가 늘어나는 경우를 손쉽게 처리하기 위함입니다.
- 마지막 원소에 1을 더합니다.
- 리스트의 끝에서부터 앞쪽으로 순회하면서 각 자릿값이 10 이상이면, 몫(올림 값)을 앞 자릿수에 더해주고 나머지를 현재 자릿값으로 설정합니다.
- 순회가 끝난 후 맨 앞 원소가 0보다 크면 그대로 반환하고, 그렇지 않으면(올림이 발생하지 않아 앞에 붙인 0이 남는 경우) 첫 번째 원소를 제외한 나머지를 반환합니다.
파이썬 구현 코드
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, n):
n = [0] + n
n[-1] += 1
for i in range(len(n) - 1, 0, -1):
n[i-1] += n[i] // 10
n[i] = n[i] % 10
return n if n[0] > 0 else n[1:]
ob = Solution()
print(ob.solve([9, 9]))
입력
[9, 9]
출력
[1, 0, 0]
동작 과정 상세 분석
입력 [9, 9]가 주어졌을 때 코드의 실행 흐름을 살펴보겠습니다.
- 맨 앞에 0을 추가하여
[0, 9, 9]가 됩니다. - 마지막 원소에 1을 더해
[0, 9, 10]이 됩니다. - 뒤에서부터 순회하면서 10을 10으로 나눈 몫 1을 앞 자릿수에 더하고, 나머지 0을 저장하여
[0, 10, 0]→[1, 0, 0]이 됩니다. - 맨 앞 원소가 1로 0보다 크므로
[1, 0, 0]을 그대로 반환합니다.
반대로 올림이 발생하지 않는 경우, 예를 들어 [2, 4, 9]에 1을 더하면 [0, 2, 5, 0]이 되고, 맨 앞의 0은 불필요하므로 [2, 5, 0]만 반환됩니다.
시간 복잡도
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 리스트의 길이입니다. 공간 복잡도 역시 새로운 리스트를 만들지 않고 기존 리스트를 수정하므로 추가 공간은 O(1) 수준입니다(맨 앞에 0을 추가하는 부분은 리스트 복사가 일어나지만, 전체적으로 효율적인 편입니다).