[LeetCode] 66. Plus One (C++)

Problem Overview

https://leetcode.com/problems/plus-one/?envType=problem-list-v2&envId=math

Plus One - LeetCode

66. Plus One

이 문제는 integer 배열로 표현된 큰 정수값에 1을 더하고 동일하게 배열로 출력하는 문제이다. 1의 자리는 가장 우측, 즉 배열 인덱스로는 마지막 인덱스가 된다.

이 문제 또한, 문제 자체는 간단하니 바로 문제를 풀어보도록 하겠다.

Approach

처음에 이 문제를 풀려고 코드를 막 작성했는데 Runtime Error가 떴다. 그 이유는 아래와 같이 코드를 작성했기 때문이다.

else if(digits[i]==9){
    digits[i] = 0;
    digits[i-1]++; 
    continue;
}

위 코드에서 만약 i가 0이 된다면, digits[i-1]은 digits[-1]에 접근하게 되어 Runtime Error가 발생한다. i=0에 대한 예외처리가 없었기 때문이다.

그래서 다음 설계를 진행하였다.

먼저 배열의 마지막 요소(가장 낮은 자릿수)부터 첫 번째 요소까지 역순으로 순회한다. 이때 현재 숫자가 9보다 작다면? 그냥 1을 더하고 즉시 배열을 반환해준다. 이 경우에는 더 이상 올림이 없으므로 종료시켜준다.

그럼, 현재 숫자가 9라면? 해당 자릿수를 0으로 만들고 다음 루프로 넘어가준다. 여기서 처음에는 digits[i-1]++;을 통해서 Carry를 한번에 처리해줄 생각이였으나, 생각해보니, 루프를 돌면 알아서 첫 번째 조건( 현재 숫자가 9보다 작을 조건 )에서 1을 더해주고 리턴을 해주게 된다. 만약 i-1 인덱스의 원래 숫자가 9여서, Carry 발생 후 10이 되어있다면? 이것도 걱정 안해도 된다. 어차피 두 번째 조건문에서 0으로 변경된다. 즉, 모든 조건을 하나하나 확인할 필요가 전혀 없었다.

이렇게 2개의 조건문으로 for문 루프가 모두 끝났는데도, 함수가 종료되지 않았다면 배열의 맨 앞에 1을 추가하고 return 해주면된다.

FOR i from last_index down to 0:
    IF digits[i] < 9:
        digits[i] += 1
        RETURN digits  // 반환
    
    digits[i] = 0     // 9였으므로 0이 되고, 루프는 계속됨 (올림 처리)

// 여기까지 왔다면 모든 숫자가 9였다는 뜻 (예: 999 -> 000)
digits의 맨 앞에 1을 삽입 (예: 1000)
RETURN digits

Code

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

 

Review

처음 생각없이 풀었을 때, Index Out of Bounds에 대한 생각을 하지 못했고, 또한 굳이 복잡한 분기 처리로 코드 효율성을 많이 떨어트렸다. (digits[i] > 9, digits[i] ==9...) 이렇게 분기를 나눠서 처리하다보니, 로직이 꼬이게 된 것 같다. 사실 문제에서 요구하는, 즉 내가 풀어야 했던 것은 10이 되는냐 아니냐라는 단순한 조건 뿐이였던 것이다. (생각해보니 11이 될 수도 없고,  어차피 9 이상이면 9와 10밖에 없는데 어차피 0으로밖에 안바뀜...멍청하다)

그래서 문제를 단순화하여 "뒤에서 앞으로" 이동하면서 자릿수 올림을 처리하는 방식으로 수정했다. 분기도 현재 숫자가 9보다 작으면 1을 더하고 배열을 반환(어차피 더 이상 캐리가 발생하지 않을 것이니) 그리고 반환이 안됐다면 해당 자릿수를 0으로 만들고, 다음 루프(앞자리)에서 1을 더하는 작업으로 진행했다.

문제의 본질을 꿰뚫는 훈련이 더 필요한 것 같다.