[python3] 989. Add to Array-Form of Integer

풀이 일자: 23.02.15

난이도: [Easy]

분류: [Array, Math]

문제 내용

int형 배열 num과 int형 변수 k가 주어졌을 때  num+k의 결과를 array형태로 리턴시키는 문제

 

 

문제 해결 흐름

저번에 풀었던 2023.02.14 - [코테/LeetCode] - [python3] 67. Add Binary문제와 사실상 비슷한 문제이다. 다만 num내부의 자료형이 int이고 결과도 int로 해야하기 때문에 저번처럼 여러번 자료형 변환을 거쳐 푸는 것은 비효율적으로 보인다.

 

1. k의 각 자리를 분리하기 위한 방법을 생각해보자.

→ 일반적인 십진수의 경우 각 자리를 구하는 방법은 반복문을 돌려가며 일의 자리를 하나씩 확인하는 방법이 존재한다.

k = 112;
ans = []

while ( k != 0):
    rm = k % 10;
    k = k // 10;
    ans.append(rm);

2. 수의 덧셈은 반드시 올림(carry)가 존재하기 때문에 일의 자리부터 계산하는 것이 좋겠다.

→ num은 배열의 끝부분부터 반대로 수를 읽고, k는 위의 방법을 사용하여 오른쪽부터 각 자리수를 구하는 방식을 사용한다.

 

3. 각 자리의 수에 carry까지 더해준다.

→ carry는 처음에 0으로 초기화주고 각 자리수와 carry의 합이 10이 넘어가는 경우 carry=1로 설정한다.

 

4. while문에서 break되는 조건을 어떻게 하면 될까?

num의 배열을 다 읽거나 k가 0이 되면 break해야한다. ( 더이상 둘의 합을 구할 필요가 없으므로)

 

5. 남은 조건 처리가 필요하다.

case1. carry == 1 and (numL < 0) and (k == 0)   => 단순히 1을 더해주면 된다.

case2. numL(num을 뒤에서 순회하는 인덱스) >= 0:    =>  carry값을 고려하여 처리한다.

case3. k != 0  =>  carry값을 고려하여 처리한다.

 

6. 조심해야 하는 특수 케이스

num = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9]와 k=1인 경우

 

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        
        ans = deque();  # reverse보다는 바로 list로 바꾸고 싶어서 deque사용.
        numL = len(num) - 1;
        carry = 0;

        while(numL >= 0 and k !=0):                     # 둘 중 하나의 수가 사용될 때까지 돌린다.
            rm = k % 10;
            s = num[numL] + rm + carry;                 # 각 자리수의 합 + 올림
            carry = 0;

            if s >= 10:                                 # 합이 10이 넘어 carry가 발생하는 경우
                carry = 1;
                s -= 10;
            ans.appendleft(s);

            k = k // 10; numL -= 1;
        
        if carry == 1 and (numL < 0) and (k == 0):       # carry만 존재하는 경우
            ans.appendleft(carry);
        else:
            if numL >= 0:                               # numL이 남은 경우(carry 존재할 수 있음)
                while(numL >= 0 or carry == 1):
                    s = carry
                    s += num[numL] if (numL >=0) else 0;
                    carry = 0;
                    if s == 10:                         #carry가 있어서 10이 되면 carry 다시 발생
                        ans.appendleft(0);
                        carry = 1;
                    else:                               # carry가 없다면 현재의 합을 더함
                        ans.appendleft(s);
                        s = 0
                    numL -= 1;

            elif k != 0:                                 # k가 남은 경우(carry 존재할 수 있음)
                s = carry + k;
                while( s != 0):
                    rm = s % 10;
                    ans.appendleft(rm);
                    s = s // 10;
        
        ans = list(ans);                                # queue를 list로 변환
        return ans;

=> 67번 문제인 Binary Sum과 비슷한 풀이를 사용하면 된다.

 

Time Complexity: O(max(n, kl) + 1)

num의 자릿수와 k의 자릿수중 최대값에 만약에 carry가 존재한다면 한 자리가 더 추가되기 때문에 O(max(n, kl) + 1)의 시간복잡도를 가진다.(queue to list)

 

Space Complexity: O(max(n, kl) + 1)

결과값을 ans에 넣기 때문에 시간복잡도와 마찬가지로 최대 O(max(n, kl) + 1)의 시간복잡도를 가진다.

 

 

다른 해결 방식(Official Solution)

1. k의 각 자리를 분해할 필요없는 방법이 있다.

→ num리스트의 맨 마지막에 k를 더해서 각 자리마다 계산을 해서 윗자리로 올리는 방법이 존재한다

 

[과정]

num = [2,1,5], k = 806

1)  우선 num[-1]에 k를 더한다

num = [2,1,811]

 

2)  num의 맨 뒷자리부터 carry를 계산한다.

carry, num[i] = divmod(num[i], 10);

carry = 81, num[i] = 1

 

3) carry를 현재 자리의 이전 자리수에 더한다.

num[i-1] += carry

num = [2,82,1];

4) 2와 3을 반복한다. (num 순회가 끝날때까지..)

num = [10,2,1];

carry = 1, num[0] = 0

 

5) 다 끝났을 때 carry가 존재하면 해당 carry를 자릿수별로 배열로 변환하고 기존의 num을 더한다.

carry = 1
carry + num = [1] + [0,2,1] = [1,0,2,1]

 

carry = 1이기에 [1]로 변환 후 + num = [0,2,1]을 하면 [1,0,2,1] 완성!!

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        num[-1] += k;
        carry = 0;
        for i in range(len(num) - 1, -1, -1):
            print(i);
            carry, num[i] = divmod(num[i], 10);
            if i:
                num[i-1] += carry;
        if carry:
            num = [int(i) for i in str(carry)] + num;
        return num

 

=> 여러 조건을 계산하지 않고 간단하게 풀 수 있는 방법

 

 

Time Complexity: O(max(N, logK))

num의 길이와 K의 log의 길이값 중 최대값을 시간복잡도로 가진다.

 

Space Complexity:  O(max(N, logK))

num의 길이와 K의 log의 길이값 중 최대값을 공간복잡도로 가진다.

 

 

문제 링크

https://leetcode.com/problems/add-to-array-form-of-integer/description/

Add to Array-Form of Integer - LeetCode