[Leetcode/C++] 66. Plus One

---

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        
        int carry = 1;
        for(int i = digits.size()-1; i >= 0; i--) {
            if(digits[i] == 9 && carry == 1) {
                digits[i] = 0;
                carry = 1;
            } else {
                digits[i] += carry;
                carry = 0;
            }
            
        }
    
        if(digits[0] == 0)  digits.insert(digits.begin(), 1);
        return digits;
    }
};

---

논리설계 수업 때 2진수 ADDER를 만들던게 생각나는 문제였습니다. carry(올림 숫자)를 추가해 9일 때 올림 숫자를 받게 되면 올림 숫자는 그대로 가져가고 자리수는 0으로 바꿔주는 형식으로 코드를 구현하였습니다.

This problem reminded me of making a binary ADDER in the logical design class. I implemented the code in the form of adding carry. if we receive the carry number 1 at 9 change number to 0.

 

마지막에 맨 앞자리가 0이 된다면 carry값을 앞에 추가해주고 return 하도록 구현하였는데 digits.insert를 삼항 연산자로 리턴할 수 없을까?하고 시도해봤지만 digits.insert는 형식이 vector<int>가 아니라서 따로 2줄로 나누어 작성하게 되었습니다.

If the first digit becomes 0, add the carry value to the front and return it's digits. I was curious about return insert function to the triangulation operator. I tried it, but the insert function is not in the form of vector<int>, so I divided it into two separate lines.

 

사실 처음 코드를 작성할 때는 마지막 부근에 digit에 insert를 하는 것이 아니라 아래 예시와 같이 1을 가진채로 기존 배열을 복사하는 것을 생각했었습니다.

At first, I thought about copying the existing array with include 1 as shown in the example below, rather than inserting it into the digit near the end.

 

그런데 흥미로운 사실은 위에 코드가 아래 코드보다 memory를 0.1 MB 더 사용한 점입니다.

Interestingly, however, the code above used 0.1 MB more memory than the code below.

 

벡터가 resizing하면서 빈공간을 많이 잡고 있게 된 것을 원인으로 생각하게 됐는데, assign을 사용했어도 결과가 동일하겠구나라는 생각을 하게 되었고 공간 복잡도를 생각하게 된다면 for문으로 직접 assign하는게 좋겠다는 생각을 하게 되었습니다.

I thought the reason was that the vector was holding a lot of empty space while resizing, and I thought that the result would be the same even if I used an adjustment, and if I thought about the space complexity, I thought it would be better to sort it directly through the for statement.

 

        vector<int> answer(digits.size() + 1);
        answer[0] = 1;
        for(int i = 0; i < digits.size(); i++) {
            answer[i+1] = digits[i];
        }
        
        return digits[0] != 0 ? digits : answer;

---

Problem : https://leetcode.com/problems/plus-one/

Plus One - LeetCode