리트코드 - 66. Plus One

리트코드 - 66. Plus One

출처 - https://leetcode.com/problems/plus-one/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

integer 배열로 표현된 큰 정수가 주어집니다. 각 digits[i]는 정수의 i번째 자릿수이며, digits는 가장 중요한 자릿수에서 가장 덜 중요한 자릿수로 왼쪽에서 오른쪽으로 정렬되어 있습니다. 이 큰 정수는 선행 0이 없습니다.

큰 정수를 하나 증가시키고, 증가된 결과의 자릿수 배열을 반환하세요.

 

의사코드

lastIndex = digits.legnth - 1 반복문 시작 (배열의 lastIndex에서 0까지)     if (digits[i] + 1 < 10)         digits[i] += 1         digits 배열 리턴     digits[i] = 0; 반복문 종료 newArr = 원래 배열보다 1크게 생성 newArr[0] = 1; newArr 배열 리턴

 

풀이코드

class Solution {
    public int[] plusOne(int[] digits) {
        int lastIndex = digits.length - 1;
        for (int i = lastIndex; i >= 0; i--) {
            if (digits[i] + 1 < 10) {
                digits[i] += 1;
                return digits;
            } 
            digits[i] = 0;
        }
        int[] newArr = new int[digits.length + 1];
        newArr[0] = 1;
        return newArr;
    }
}

 

코드설명

입력 숫자가 배열로 주어질 때 +1 한 다음 수를 구하는 문제이다.

여러가지 방법이 있겠지만 가장 핵심이 되는 로직은 '합이 10이 되었을때 다음 자리수에 더하는가?'가 될 것이다.

또 '모든 자리수가 9인 경우라면 자리수가 하나 추가되어야 한다.'는 조건도 있다.

배열은 크기를 바꿀수 없으니 새로운 배열이 필요할 것이다.

 

먼저 덧셈을 하기위해 반복문을 돌려 마지막 자리부터 더한다.

1을 더했을때 10보다 작은 수라면 1을 더해주고 배열을 리턴한다. 더 더할것이 없기 때문이다.

 

만약 10이 되는 경우라면 if문을 빠져나오고 해당 자리수를 0을 만들어주면 된다.

반복문에 의해 다음 자리를 계산하게 된다.

 

반복문이 모두 끝날때까지 입력된 배열을 리턴하지 않는다면 모든 자리가 다 올림이 된 것이다.

 

따라서 크기가 하나 큰 배열을 만들고, 배열 첫째값을 1로 만들고 리턴하면 해결된다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public int[] plusOne(int[] digits) {
        int lastIndex = digits.length - 1;
        boolean isContinue = true;
        for (int i = lastIndex; i >= 0; i--) {
            if (isContinue) {
                if (digits[i] + 1 < 10) {
                    digits[i] += 1;
                    isContinue = false;
                } else if (digits[i] + 1 == 10) {
                    if (i == 0) {
                        int[] newArr = new int[digits.length + 1];
                        newArr[i] = 1;
                        return newArr;
                    }
                    digits[i] = 0;
                    isContinue = true;
                }
            }
        }
        return digits;
    }
}

처음에는 한 메소드에 때려(?)박고, 리팩토링을 했다.

 

그렇지만 else if문이 심하게 거슬려서 if문에서 걸러지고, 그렇지 않으면 뭔가 작업을 하는 코드로 바꾸고자 한게 풀이코드다.

풀다보니 재귀적인 방법으로도 풀 수 있지 않을까 해서 생각해봤다.

 

재귀 풀이

class Solution {
    public int[] plusOne(int[] digits) {
        return addWithCarry(digits, digits.length - 1);
    }

    private int[] addWithCarry(int[] digits, int index) {
        if (index < 0) {
            int[] newArr = new int[digits.length + 1];
            newArr[0] = 1;
            return newArr;
        }

        if (digits[index] + 1 < 10) {
            digits[index] += 1;
            return digits;
        } 
        digits[index] = 0;
        return addWithCarry(digits, index - 1);
    }
}

로직에는 크게 차이가 없다.

단지 차이가 있다면 재귀적으로 구현하고 다른 메소드에게 위임했다는 점이다.

 

더 리팩토링을 하면 이런 코드가 된다.

 

극단적(?) 리팩토링

class Solution {
    public int[] plusOne(int[] digits) {
        return addWithCarry(digits, digits.length - 1);
    }

    private int[] addWithCarry(int[] digits, int index) {
        if (index < 0) {
            int[] newArr = new int[digits.length + 1];
            newArr[0] = 1;
            return newArr;
        }

        if (++digits[index] == 10) {
            digits[index] = 0;
            return addWithCarry(digits, index - 1);
        } 
        return digits;
    }
}

사실 이렇게 다 해도 런타임은 모든 코드가 0ms이고, 메모리 차이도 크지 않다.

그냥....기교에 가까운 것 같다.

 

정리

배열로 숫자가 주어졌을때 덧셈을 하는 방법에 대한 문제