[리트코드] 66 Plus One

Plus One

문제를 딱 보면 그냥 단순하게 뒤에서부터 하나씩 증가하는 즉, ++을 구현하는 문제입니다.

첨엔 그냥 시간복잡도나 그런거 신경 안쓰고 생각나는대로 바로 풀어봤습니다. 그랬더니 어마어마한 시간이랑 공간이 나오게 되었고…

좀 더 줄여볼까 하고 스택을 사용해봤더니 그나마 좀 짧게 나왔습니다.

풀이는 다음과 같습니다.

Source Code:

//벡터만 이용해서 풀어본 풀이 -> reverse가 들어간다. 

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

// stack 사용해본 풀이
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        
        int carry = 1;
        vector<int> answer; 
        stack<int> st;
        
        for(int i=digits.size()-1;i>=0;i--){
            int digit = digits[i] + carry;
            if(digit < 10){
                carry = 0;
                st.push(digit);
            }else{
                carry = 1;
                st.push(0);
            }
        }
        
        if(carry == 1)
            st.push(1);
        
        while(!st.empty()){
            answer.push_back(st.top());
            st.pop();
        }
        
        
        return answer;
    }
};

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 리트코드 재밌네요