문제 소개
어떤 수의 각 자릿수가 nums라는 리스트에 저장되어 있다고 가정해 보겠습니다. 예를 들어 [2, 5, 6]은 256을 나타냅니다. 이제 이 수에 1을 더한 결과를 동일한 형식, 즉 자릿수 리스트 형태로 반환해야 합니다.
예를 들어 입력이 nums = [2, 6, 9]라면, 269 + 1 = 270이므로 출력은 [2, 7, 0]이 됩니다.
알고리즘 접근 방법
핵심 아이디어는 우리가 손으로 덧셈을 할 때와 마찬가지로, 가장 뒤쪽 자릿수부터 차례대로 처리하면서 받아올림(carry)을 앞쪽으로 전파하는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- i := len(nums) - 1 : 리스트의 마지막 인덱스부터 시작합니다.
- i >= 0인 동안 반복 :
- 만약 nums[i] + 1이 9 이하라면 → nums[i]를 1 증가시키고 반복문을 빠져나옵니다.
- 그렇지 않다면(현재 자릿수가 9라면) → nums[i]를 0으로 만들고 i를 1 감소시켜 앞 자릿수로 넘어갑니다. 이것이 바로 받아올림 처리입니다.
- 반복문 종료 후 i < 0이라면 : 모든 자릿수가 9였다는 의미이므로(예: 999 + 1 = 1000), 리스트 맨 앞에 1을 삽입합니다.
- nums를 반환합니다.
파이썬 구현 코드
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
def solve(nums):
i = len(nums) - 1
while i >= 0:
if nums[i] + 1 <= 9:
nums[i] = nums[i] + 1
break
else:
nums[i] = 0
i -= 1
if i < 0:
nums.insert(0, 1)
return nums
nums = [2, 6, 9]
print(solve(nums))입력
[2, 6, 9]
출력
[2, 7, 0]
실행 과정 상세 설명
입력이 [2, 6, 9]일 때 코드가 동작하는 과정을 단계별로 살펴보겠습니다.
- 마지막 자릿수 9에 1을 더하면 10이 되어 한 자릿수 범위를 벗어나므로, 해당 자릿수를 0으로 바꾸고 앞 자릿수로 받아올림합니다. → [2, 6, 0]
- 다음 자릿수 6에 받아올림된 1을 더하면 7이 되고, 9 이하이므로 여기서 반복문을 종료합니다. → [2, 7, 0]
- 최종 결과 [2, 7, 0]이 반환됩니다.
반면 입력이 [9, 9, 9]처럼 모든 자릿수가 9라면, 반복문이 끝날 때까지 모든 자릿수가 0으로 바뀌고 i는 -1이 됩니다. 이 경우 조건문에 의해 리스트 맨 앞에 1이 삽입되어 [1, 0, 0, 0], 즉 1000이라는 올바른 결과를 얻게 됩니다.
복잡도 분석
시간 복잡도는 최악의 경우(모든 자릿수가 9인 경우) 리스트 전체를 한 번 순회하므로 O(n)입니다. 공간 복잡도 역시 자릿수가 하나 늘어나는 최악의 경우를 제외하면 O(1)이며, 새 리스트가 필요할 때만 O(n)입니다.