[코딩연습] Plus One 배열을 정수로 보고 1 더하기

LeetCode 문제 중 난이도 Easy인 Plus One이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

비어있지 않은 배열의 숫자들이 음수가 아닌 정수를 나타낸다고 하자. 그 정수에 1을 더하여라.

가장 큰 수부터 저장되고(앞에서부터 읽으면 된다는 뜻) 배열의 각 요소들은 한 자리의 숫자들을 가지고 있다.

정수는 값이 0일 경우를 제외하고 0으로 시작하지 않는다고 가정한다.

Example 1 : 정수 123에 1을 더하면 124이므로 [1,2,4] 출력

Example 2 : 정수 4321에 1을 더하면 4322이므로 [4,3,2,2] 출력

이 문제를 어떻게 해결할까? 먼저 Example 1과 2의 예시처럼 가장 간단한 경우의 수를 생각해보자.

배열의 맨 마지막 숫자에 +1을 해 주면 간단하게 해결 될 것이다.

class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        digits[len-1]=digits[len-1]+1;
 
        return digits;
    }
}

** 배열(뿐만 아니라 어떤 자료형을 사용하든지간에)값이 null인지 확인하는 예외처리는 가장 기본이지만 이 문제에서는 배열이 비어있지 않다고 했으므로 파라미터로 넘어오는 digits 배열이 null이거나 배열의 length가 0인 경우에 대한 예외처리는 생략한다.

배열의 마지막 숫자가 9일 땐 어떨까? 위의 코드대로라면 Input값이 [5,3,9]일 경우 Output으로 [5,4,0]대신[5,3,10]이 나온다. 각 배열의 요소는 한 자리의 숫자로 이루어져야 하므로 위의 코드에서 배열의 값이 10 이상일 경우 자리수를 하나씩 올려주는 carry()함수를 추가하고 for문을 이용해 배열을 뒤에서부터 탐색하여 자리수를 올려준다.

class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        digits[len-1]=digits[len-1]+1; //배열의 마지막 값에 1을더함
 
        //그 값이 10보다 작으면(자리수가 안바뀌면) 그냥 그대로 리턴
        if(digits[len-1]<10){    
            return digits;
        }
 
        //10이상이면(9보다크면) 하나씩 올림한다
        for(int i=len-1 ; i>0 ; i--){
            if(digits[i]>9){
                carry(i,digits);
            }
        }
 
        return digits;
    }
    
    public void carry(int index,int[] digits){
        digits[index]=0;
        digits[index-1]=digits[index-1]+1;
    }
}

carry(index,digits)는 인덱스와 배열 자체를 파라미터로 받아 배열의 해당 인덱스 값이 10 이상일 경우 그 값을 0으로 만들고 배열의 인덱스-1 값에 +1을 해준다. 이 때 digits[0]이 10인 경우에는 digits[-1]가 존재하지 않으므로 digits[1]인 경우 까지만 체크하고 일단 넘어간다.

자리수를 올려주는 부분은 초등학교 때 배운 받아올림이 있는 덧셈을 생각하면 된다.

이제 거의 다 왔다! 위에서는 배열의 요소가 전부 9인 경우는 고려하지 않았다. 만일 배열의 모든 요소가 9인 경우, for문을 돌고 난 뒤 배열의 상태는 [10,0,······] 일 것이다. digits[0]에서는 더 이상 앞으로 올림해 줄 수가 없으므로 이 경우에는 배열의 크기를 1 늘리고 [1,0,0,······]으로 채워주어야 한다. 

class Solution {
    public int[] plusOne(int[] digits) {
        
        int len = digits.length;
        digits[len-1]=digits[len-1]+1; //일단 배열의 마지막 값에 1을 더함
 
        //10보다작으면(자리수가 안바뀌면) 그냥 그대로 리턴
        if(digits[len-1]<10){    
            return digits;
        }

        //10이상이면(9보다크면) 하나씩 올림한다
        for(int i=len-1 ; i>0 ; i--){
            if(digits[i]>9){
                carry(i,digits);
            }
        }

        //배열의맨앞숫자가 10이면 배열의 크기를 1 늘리고 1000...으로 채워준다
        if(digits[0]>9){
            int[] newDigits = new int[len+1];
            newDigits[0]=1;
            for(int i=1 ; i<newDigits.length ; i++){
                newDigits[i]=0;
            }
            return newDigits;
        }
        return digits;
    }
    
    public void carry(int index,int[] digits){
        digits[index]=0;
        digits[index-1]=digits[index-1]+1;
    }
}

자 이제 완성된 코드를 돌려 보자!

Worst case는 배열의 모든 요소가 9일 경우 이므로 이 때 시간복잡도는 O(n), 공간복잡도도 O(n)이다.

2019/02/25 - [프로그래밍문제풀기] - 빅오표기법(Big O notation)

문제 출처 링크 - https://leetcode.com/problems/plus-one