Plus One

123 같은 숫자를 {1,2,3}으로 쪼개서 vector로 주어진다. 여기에 1을 더해서 vector로 반환하는 문제이다.

123+1 = 124 이니 {1,2,4}로. 9라면 {1,0}으로.

처음에는 간단하게

1. vector에서 값을 추출해 숫자로 만듦. 1,2,3 -> 3+20+100

2. ++ 해준다. 124

3. stack에 넣어 역순으로 저장 4,2,1

4. push_back으로 stack에서 큰 자리수부터 저장. 1,2,4

5. 반환

이렇게 생각하고 제출했다.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //insert front -> vector.insert(vector.begin(), value)
        int loop = digits.size();
        if (digits[loop - 1] < 9)
        {
            digits[loop - 1]++;
            return digits;
        }
        int num = 0;
        for (int i = 0; i < loop; ++i)
        {
            num += pow(10, i) * digits.back();
            digits.pop_back();
        }

        num++;
        stack<int> s;

        while(num>0)
        {
            s.push(num % 10);
            num /= 10;
        }
        loop = s.size();
        for (int i = 0; i < loop; ++i)
        {
            digits.push_back(s.top());
            s.pop();
        }

        return digits;
    }
};

 

근데, int형 범위를 넘어서는 값이면 안되더라 ^^; 그래서 vector가지고 푸는 방법을 생각해야 했다.

4ms, 8.9MB. 50% 수준의 속도라 뭐지하고 다른 사람들 것도 찾아봤는데 다들 O(n)이어서 여기서 끝.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //insert front -> vector.insert(vector.begin(), value)
        int loop = digits.size()-1;
        for (int i = loop; i >= 0; --i)
        {
            if (digits[i] != 9) //9가 아니라면 그냥 1더해주면 된다.
            {
                digits[i] += 1;
                return digits;
            }
            //9라면 0으로 만들어준다. 다음 숫자가 0이 아니라면 +1해주고 끝일거고,
            //9라면 똑같이 0이 되고 그 다음 숫자로 for문 타고 넘어간다.
            else
            {
                digits[i]=0;
                if (i == 0)
                    digits.insert(digits.begin(), 1);
            }
        }
        return digits;
    }
};

방식은 다음과 같다. 9가 아닌 경우에야 그냥 더하고 return하면 끝이지만, 9인 경우를 처리해야한다.

초등학교 때 배운 방식으로는 9에 1을 더하면 0이 되고 다음 자리수에 1을 더하지 않던가?

for문으로 어차피 자리수를 넘기면서 1을 더해줄 것이므로 9에 1을 더하는 경우는 0으로만 만들어주면 된다.

관건은 가장 큰 자리수인 idx=0인 경우. insert라는 좋은 기능으로 가장 첫자리에 1을 심어주면 가장 큰 자리수가 9인 경우도 처리된다. 그리고나서 return해주면 끝.