해결 날짜: 2015년 2월 23일
난이도: (쉬움)
분류: (배열, 수학)
![[이코테] 실전 문제](https://post.storylook.kr/wp-content/plugins/contextual-related-posts/default.png "[이코테] 실전 문제")
문제에 대한 설명
int 타입의 배열 번호와 int 타입의 변수가 주어졌을 때 num+k 결과를 배열 형태로 반환하는 문제 수정
문제 해결 흐름
2023.02.14 – (Kote/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. 숫자를 더할 때 항상 자리올림이 있기 때문에 일의 자리부터 시작하는 것이 좋습니다.
→ num은 배열의 끝에서 거꾸로 숫자를 읽고, k는 위의 방법을 사용하여 오른쪽부터 각 숫자를 찾습니다.
3. 각 숫자에 캐리를 추가합니다.
→ 캐리는 초기에 0으로 초기화되며 각 자릿수와 캐리의 합이 10을 초과하면 캐리=1로 설정됩니다.
4. while 문에서 중단 조건을 설정하려면 어떻게 해야 합니까?
num에서 배열을 읽거나 k가 0이 되면 중단합니다.
(더 이상 둘의 합을 찾을 필요가 없기 때문에)
5. 나머지 조건을 처리해야 합니다.
사례 1. 나르다 == 하나 그리고 (No.L 0) 그리고 (케이 == 0) => 1을 더하면 됩니다.
case2. numL(인덱스는 num을 거꾸로 반복함) >= 0: => 캐리 값을 고려하여 처리합니다.
case3. 케이!
= 0 => 캐리 값을 고려하여 처리됩니다.
6. 특별한 경우에 주의하라
숫자 = (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;
=> Exercise 67 Binary Sum에 대해 유사한 솔루션을 사용할 수 있습니다.
시간 복잡도: O(max(n, kl) + 1)
올림이 있으면 num의 자릿수와 k의 자릿수 최대값에 한 자릿수를 더한다.
O(최대(n,kl) + 1)시간 복잡도는 (queue to list)입니다.
공간 복잡도: O(최대(n,kl) + 1)
결과 값이 ans에 입력되기 때문에 최대 O(최대(n,kl) + 1)의 시간복잡도를 갖는다
다른 해결 방법(공식 솔루션)
1. k의 각 자릿수를 분해할 필요가 없는 방법이 있습니다.
→ 숫자 목록 끝에 k를 더해서 각 자릿수를 계산해서 맨 위로 가져오는 방법이 있습니다.
(절차)
num = (2,1,5), k = 8061) 먼저 k를 num(-1)에 더합니다.
num = (2,1,811)
2) num의 마지막 자릿수에서 캐리 아웃을 계산합니다.
carry, num(i) = divmod(num(i), 10);
carry = 81, num(i) = 1
3) 현재 자리의 이전 자리에 캐리를 더합니다.
num(i-1) += carry
num = (2,82,1);4) 2번과 3번을 반복한다.
(num traversal이 끝날 때까지…)
num = (10,2,1);
carry = 1, num(0) = 0
5) 완료되면 캐리가 있으면 숫자별로 배열로 변환하고 기존 숫자를 추가하십시오.
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문제가 있는 링크
https://leetcode.com/problems/add-to-array-form-of-integer/description/
배열 형태의 정수에 추가 – LeetCode
정수의 배열 형식에 추가 – 정수의 배열 형식은 왼쪽에서 오른쪽 순서로 숫자를 나타내는 배열입니다.
* 예를 들어 num = 1321인 경우 배열 형식은 (1,3,2,1)입니다.
주어진 num, 정수의 배열 형식 및 정수 k는 ar을 반환합니다.
leetcode.com