Leet Code - 66. Plus One(C++)

예제: Plus One

문제
Share
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

풀이

처음 문제를 슥 보고 이렇게 쉽다고? 하고 생각했었는데, 역시 조금 더 생각해보니 그렇게 쉬울리가 없었다.
[9] 일 수도 있고, [9, 9, 9] 일 수도 있는 것이다. 1을 넘겨주어야 한다는 뜻이다.

필자는 10을 넘어갈 경우만 다음 차례를 보며, digits[0]도 10을 넘어가는 경우, 즉 digits의 크기가 커져야 하는 경우는, insert 함수를 써서 digits의 첫 번째 자리에 1을 삽입해 주었다.

따라서 [9] 인 경우는 [1, 0]이 return되는 것이다.

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	vector<int> plusOne(vector<int>& digits) {
		if (digits.size() == 0) return {};

		digits[digits.size() - 1]++;
		for (int i = digits.size() - 1; i >= 0; i--) {
			if (digits[i] > 9) {
				digits[i] %= 10;
				if (i == 0) digits.insert(digits.begin(), 1);
				else digits[i - 1]++;
			}
			else {
				break;
			}
		}

		return digits;
	}
};

풀이 후기

집안 문제로 알고리즘을 4일정도 못 풀었더니, 벌써 몸과 머리가 굳은 느낌이다.
감각이여 살아나라!