[neetcode] Plus One

난이도

• Easy

  문제 설명

  정수 배열 digits가 주어지며, 각 digits[i]는 큰 정수의 i번째 자릿수입니다. 이 배열은 가장 중요한 자릿수(최상위)부터 가장 덜 중요한 자릿수(최하위)까지 순서대로 정렬되어 있으며, 선행 0은 포함하지 않습니다. 주어진 정수에 1을 더한 후의 자릿수를 배열로 반환하세요.

입력 형식

• 정수 배열

출력 형식

• 정수 배열열

예제 입력 및 출력

**예제 1:**
출력 : digits = [1,2,3,4]
입력 : [1,2,3,5]

예제 2:

출력 : digits = [9,9,9]
출력: [1,0,0,0]

접근 방법

• 값이 9 면 0으로 변경하고, 올림을 true로 수정
• 값이 9가 아니면, 올림할 필요가 없으므로 해당값을 1 추가하고, 반복문을 종료료

시간 및 공간 복잡도

• 시간 복잡도: O(n) - 모든 배열을 한번 순회해야함
• 공간 복잡도: O(1), O(n) - 기존 배열을 사용, 새 배열을 생성해야하는 경우(올림) 공간복잡도가 O(n)으로 변경

코드 구현

class Solution {
    public int[] plusOne(int[] digits) {
        int num = 1;
        boolean carry = true;
        for(int i = digits.length - 1; i >= 0; i--){
            if(digits[i] == 9){
                digits[i] = 0;
            }else{
                carry = false;
                digits[i]++;
                break;
            }
        }
        if(carry){
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }
        return digits;
    }
}