[LeetCode/EASY] 66. Plus One (JAVA) : 문제&풀이

 

 

각 자릿수가 배열로 주어진 하나의 수에 1을 더한 값을 각 자릿수 배열로 반환하는 문제이다.

e.g. [9, 9, 9] → 999 + 1 = 1000 → [1, 0, 0, 0]

 

int 배열을 매개변수로 받는 plusOne 메서드의 틀이 주어진다.

 

Problem : 

public class PlusOne {
    public int[] plusOne(int[] digits){
    
    }
}

풀이는 주어진 plusOne 메서드에 작성하면 된다.

 

Solution :

1. 주어진 숫자배열의 맨뒤(=1의 자리수)에 1을 더하고, 그 수의 1의 자리수만 저장한다.
   (9 + 1 = 10이 되었을 때, 1의 자리수에 0만 저장하기 위함)
2. 저장한 수가 0인 경우 한자리 올림수(carry)가 발생한 것이므로 carry를 1로 설정하고 다음 자리수로 넘어가 1번 내용을 반복한다.
3. 저장한 수가 0이 아닌 경우 carry는 0이므로 반복문을 멈춘다.
4. 끝까지 다 돌았을 때 carry가 1이면, 주어진 수보다 한자리수가 더 큰 수가 된다는 뜻이므로, 해당 크기의 새로운 숫자 배열을 생성하고, 첫번째 인덱스만 1로 설정한다.
   (99 + 1 = 100, 999 + 1 = 1000 등의 경우)

public class PlusOne {

    // time complexity : while loop -> O(n)
    // space complexity : the worst case creating a new array -> O(n)
    public int[] plusOne(int[] digits){

        int carry = 1;
        int index = digits.length - 1;

        while(index >= 0 && carry > 0){
            digits[index] = (digits[index] + 1) % 10;
            carry = (digits[index] == 0)? 1 : 0;

            index--;
        }

        if(carry > 0) {
            digits = new int[digits.length + 1];
            digits[0] = 1;
        }

        return digits;
    }
}

 

이해하기 쉽게 예시를 그림으로 표현하면 다음과 같다.

---

 

Complexity :

• 시간복잡도 (Time Complexity)
  • 주어진 숫자배열 길이에 따라 while문 반복하므로 O(n)
• 공간복잡도 (Space Complexity)
  • 최악의 경우에 주어진 배열의 +1 크기의 배열을 생성하므로 O(n)
  • 그 외의 경우에는 주어진 배열을 그대로 사용하므로 O(1)

 

Sample(Test) :

import java.util.Arrays;

public class PlusOne {

    // time complexity : while loop -> O(n)
    // space complexity : the worst case creating a new array -> O(n)
    public int[] plusOne(int[] digits){

        int carry = 1;
        int index = digits.length - 1;

        while(index >= 0 && carry > 0){
            digits[index] = (digits[index] + 1) % 10;
            carry = (digits[index] == 0)? 1 : 0;

            index--;
        }

        if(carry > 0) {
            digits = new int[digits.length + 1];
            digits[0] = 1;
        }

        return digits;
    }

    public static void main(String[] args){
        int[] digits = new int[] {9,9,9};

        PlusOne p = new PlusOne();
        System.out.println(Arrays.toString(p.plusOne(digits)));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[1, 0, 0, 0]