[leetCode] 66. Plus One (Easy) 풀이

 

❓ 문제

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer.

정수 배열 자릿수로 표현되는 큰 정수가 주어집니다. 여기서 각 자릿수[i]는 정수의 i번째 자릿수입니다.

 

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.

숫자는 왼쪽에서 오른쪽 순서로 최상위에서 최하위 순으로 정렬됩니다. 큰 정수에는 선행 0이 포함되지 않습니다.

 

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

큰 정수를 1씩 증가시키고 결과 배열을 반환합니다.

❗ 내 답변

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    digits[digits.length - 1] += 1;
    for (let i = digits.length - 1; i >= 0; i--) {
        if (Math.floor(digits[i] / 10) <= 0) continue;
        const curNum = digits[i];
        digits[i] %= 10;
        digits[i - 1] = digits[i - 1] + (curNum / 10);
        if (!digits[i-1])
            digits.unshift(curNum / 10);

    }
    return digits; 
};

처음엔 주어진 배열을 join()으로 합치고 Number()로 숫자형으로 바꾼다음 1을 더해주고,
그 값을 split('') 해서 리턴하려고 했었다.
그런데 범위를 넘어 가는 값이 제대로 계산되지 않아, 한자리씩 계산해주는 방법으로 수정했다.

 

배열의 뒤에서 부터 반복을 돌게했다.
현재 요소가 한자리 수이면 continue 로 넘어가고,
두자리 수 이상일 때,
10으로 나눈 나머지 값을 현재 값으로 바꾸고
10으로 나눈 몫을 앞 요소에 더해준다.

[9] 같은 경우 [1,0]으로 기존에 존재하지 않는 자리가 추가되어야하기 때문에
unshift()를 사용했다.

❗ Runtime이 가장 빨랐던 답변과 비교

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    let carry = 1;

    for (let i = digits.length - 1; i >= 0; i--) {
        const t = digits[i] + carry;
        digits[i] = t % 10;
        carry = parseInt(t / 10, 10);
        if (carry === 0) {
            return digits;
        }
    }

    digits.unshift(carry);

    return digits;
};

나와 거의 비슷한 방법이지만 훨씬 깔끔하다.

 

뒤에서 부터 반복 돌면서 1(carry)를 더하는데,
더한 값의 10을 나눈 나머지를 현재 요소로 바꾼다.
carry는 요소를 바꾸고 난 뒤 원래 요소를 10으로 나눈 값의 몫으로 변경된다.
그리고 carry가 0이라면 그래도 digits를 반환한다.
반복을 다 돈 다음엔 carry를 unshift() 시켜준다.

 

예) [9, 9]

첫번째 반복,
t는 9에 1이 더해진 10이 되고,
현재 요소는 10으로 나눈 나머지 값인 0이된다.
carry 는 10으로 나눈 몫인 1이 된다.

carry 가 0인 경우는 요소가 한자리 수여서 10으로 나눈 몫이 0인 경우를 뜻한다.
즉, 바로 digits 를 반환해도 문제 없는 것.

❗ Memory 사용이 가장 적었던 답변과 비교

function plusOne(digits) {
    let carry = 1;

    for (let i = digits.length - 1; i >= 0; i--) {
        let num = digits[i] + carry;
        carry = 0;

        if (num > 9) {
            num -= 10;
            carry = 1;
        }

        digits[i] = num;
    }

    return carry ? [1, ...digits] : digits
}

/나 %를 사용 않고, 9 이상인지 직접적으로 확인하고 10을 뺐다.
carry 역시 1과 0을 직접 선언해주고 있다.
이는 digits의 요소가 모두 한자리 수이고 1이라는 작은 수를 더하기 때문에 가능한 것이다.

💡 개선 방안

복잡하게 생각하지 말고, 불필요한 코드를 줄이자.