66. Plus One

Description

You are given a large integer represented as an integer array digits, where each digits[i] is the i^th digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Example 1:

• Input: digits = [1,2,3]
• Output: [1,2,4]
• Explanation: The array represents the integer 123.
  Incrementing by one gives 123 + 1 = 124.
  Thus, the result should be [1,2,4].

Example 2:

• Input: digits = [4,3,2,1]
• Output: [4,3,2,2]
• Explanation: The array represents the integer 4321.
  Incrementing by one gives 4321 + 1 = 4322.
  Thus, the result should be [4,3,2,2].

Example 3:

• Input: digits = [9]
• Output: [1,0]
• Explanation: The array represents the integer 9.
  Incrementing by one gives 9 + 1 = 10.
  Thus, the result should be [1,0].

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0’s.

Submitted Code

class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        last_digit = len(digits) - 1          # 현재 계산하는 자리의 인덱스를 가리키는 포인터

        while last_digit >= 0:                # 인덱스가 -1이 되기 전까지 반복
            digits[last_digit] += 1           # 현재 계산하는 자리의 원소값에 +1

            if digits[last_digit] == 10:      # +1을 한 결과가 10이면(9 + 1 = 10)
                digits[last_digit] = 0          # 원소값을 0으로 변경
                last_digit -= 1                 # 계산하는 자리를 한 칸 전진
            else:                             # +1을 한 결과가 10이 아니면
                return digits                   # 바로 digits 반환
        
        digits.insert(0, 1)                   # while문에서 반환되지 않았다면 맨 앞에 1을 추가 후 반환
        return digits

Runtime: 0 ms | Beats 100.00%
Memory: 12.50 MB | Beats 22.93%

리스트의 길이가 n일 때 시간 복잡도는

최악의 경우 digits의 모든 자리가 9이기 때문에 전부 순회해야 해서 𝑂(𝑛)이고,
.insert() 함수는 리스트의 모든 요소를 뒤로 한 칸씩 밀고 맨 앞에 원소를 추가하기 때문에 𝑂(𝑛)이어서
결과적으로 𝑂(𝑛) + 𝑂(𝑛) = 𝑂(𝑛)이 된다.

Other Solutions

1st

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:

        for i in range(len(digits) - 1, -1, -1):

            if digits[i] + 1 != 10:       # 원소값에 +1을 한 값이 10이 아니면
                digits[i] += 1              # +1을 하고 반환
                return digits
            
            digits[i] = 0                 # 위의 if문을 만족하지 않았다면 원소값을 0으로 변경

            if i == 0:                    # i가 0인 경우 [1]과 digit을 합해서 반환
                return [1] + digits

time complexity: 𝑂(𝑛)
space complexity: 𝑂(𝑛)

[1] + digits는 실제로 [1]과 기존 digits를 복사해서 더한 새 리스트를 생성하기 때문에 공간 복잡도가 𝑂(𝑛)이 된다.

2nd

class Solution:
    def plusOne(self, digits):
        strings = ""
        for number in digits:
            strings += str(number)

        temp = str(int(strings) +1)

        return [int(temp[i]) for i in range(len(temp))]

int 타입인 digits의 원소를 str으로 변환하여 해결한 예시이다.

다만 문자열끼리 더해서 연결할 때 기존의 문자열을 복사하여 새로운 문자열을 생성하기 때문에 비효율적이다.

3rd

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return [int(num) for num in str(int(''.join(map(str, digits))) + 1)]

두 번째 예시와 비슷하나, 리스트 컴프리헨션과 .join() 함수를 이용해 한 줄로 구현된 코드이다.

digits = [1,2,3]

1. .map() 함수로 digits의 각 요소를 str로 변환: [1,2,3] → [“1”, “2”, “3”]
2. join 함수로 리스트의 문자들을 공백없이 이어붙임: [“1”, “2”, “3”] → “123”
3. int로 연결된 문자열을 정수로 변환: “123” → 123
4. 변환된 정수에 1 더하기: 123 + 1 = 124
5. 1을 더한 결과를 다시 str로 변환: 124 → “124”
6. 문자열의 각 문자를 다시 정수로 변환하여 새 리스트 생성: “124” → [1,2,4]

digits = [1,2,4]