[알고리즘] LeetCode 66번 "Plus One" (C/C++) - Don 임베디드

문제요약:

When given array of integers called digits, that presents decimal digits one by one,

return the result of the (number + 1) in the same format.

Digits[i] represent the ith digit of a number.

Digits are ordered from most significant to least significant in left-to-right order.

The digits does not contain any leading 0's.

 

 

제약:

1 <= digits.length <= 100

0 <= digits[i] <= 9

digits does not contain any leading 0's.

 

예제 1 입력.	예제 1 출력.
[4,3,2,1]	[4,3,2,2]
예제 2 입력.	예제 2 출력.
[9]	[1,0]
예제 3 입력.	예제 3 출력.
[1,6,9,9]	[1,7,0,0]

 

 

정답코드:

class Solution {
public:
    vector<int> plusOneDigit(vector<int>& digits, int nIdx)
    {
        if (digits[nIdx] < 9)
        {
            digits[nIdx]++;
            return digits;
        }
        else if (digits[nIdx] == 9)
        {
            digits[nIdx] = 0;
            if (nIdx == 0)
            {
                // create digits with extra digit.
                // std::vector doesn't does not offer push_front interface.
                digits.insert(digits.begin(), 1);
                return digits;
            }
            else
            {
                nIdx--;
                return plusOneDigit(digits, nIdx);
            }
        }
        else
        {
            cout << "error case!!!" << endl;
            return digits;
        }
    }
    
    vector<int> plusOne(vector<int>& digits) {
        
        return plusOneDigit(digits, digits.size()-1);
    }
};

 

핵심 Idea:

1. Recursive function.

2. std::vector 는 push_front 인터페이스를 제공하지 않음.

    v.insert(v.begin(), element); // 이런 식으로 사용하면 됨.

 

 

원본 링크: https://leetcode.com/problems/plus-one/