Leetcode 66. Plus One - Easy

이번 문제는 한자리 숫자들로 이루어진 배열을 입력받아서 처리하는 겁니다.

그 숫자들로 구성된 한 숫자에 1을 더하는 겁니다.

즉 [1,2,3] 이면 123으로 생각해서 여기에 1을 더한 124를 한자리 숫자들로 이뤄진 배열인 [1,2,4] 로 만들어 반환하면 됩니다.

 

여기에는 세가지 경우의 수가 있습니다.

위와 같이 배열의 마지막 숫자가 9가 아니면 단순히 그 숫자에 1을 더하면 됩니다.

 

그런데 마지막 숫자가 9인 경우는 조금 다르게 접근 해야 합니다.

 

[1,2,9] 인 경우는 129가 되고 여기에 1을 더하면 130이 됩니다. 그러면 리턴값은 [1,3,0] 이 됩니다.

이 경우는 9인 값은 0이 되고 그 이전 값 중 9가 아닌 숫자에 1을 더하면 됩니다.

[8,9,9] 인 경우는 899가 되서 900으로 계산 되고 리턴값은 [9,0,0] 이 되겠죠.

 

한가지 경우가 더 있습니다.

 

모든 숫자들이 9인 경우입니다.

[9,9,9] 인 경우는 999 + 1 이 되서 1000이란 값이 계산 됩니다. 그럼 리턴 값은 [1,0,0,0] 이 됩니다.

모든 9는 0으로 되고 아이템을 하나 더 만들어서 그 값은 1로 해야 됩니다.

 

다음 3가지 조건을 만족하는 로직을 만들어야 합니다.

 

1. 맨 마지막 숫자가 9가 아닌 경우 : 마지막 숫자에 1을 더함

2. 마지막 숫자가 9 이 고 이전의 숫자 중 9가 아닌 숫자가 있는 경우 : 9를 0으로 바꾸고 9가 아닌 숫자에 1을 더하고 마친다.

3. 모든 숫자가 9인 경우 : 모든숫자를 0으로 바꾸고 맨 앞에 1을 하나 붙인다. (배열 크기가 하나 더 큰 새로운 배열을 만들어야 한다.

 

내가 만든 로직은 아래와 같습니다.

 

class Solution {
    public int[] plusOne(int[] digits) {
        
        int inputLeng = digits.length;
        
        if(digits[inputLeng-1] == 9) { // if last number is 9
            boolean allNine = true;
            for(int i=0; i < inputLeng - 1; i++) { // check if all numbers are 9
                if(digits[i] != 9) {
                    allNine = false;
                } 
            }
            if(allNine) { // if all 9s
                int[] newDigits = new int[inputLeng + 1]; // create new array (length is input + 1)
                newDigits[0] = 1; // first one is 1
                for(int n=1; n < inputLeng-1; n++) { // all others are 0
                    newDigits[n] = 0;
                }
                return newDigits;
            } else { // if at least one number is not 9
                for(int j=inputLeng-1; j >= 0; j--) {
                    if(digits[j] != 9) {
                        digits[j] = digits[j] + 1; // not 9 + 1
                        break; // escape for loop
                    }
                    digits[j] = 0; // not 9 should be 0
                }
            }
        } else { // if last number is not 9 then just +1
            int plusOne = digits[inputLeng-1] + 1;
            digits[inputLeng-1] = plusOne;
        }
        return digits;
    }
}

 

이것을 조금 더 간단하게 리팩토링 해서 만든 것이 아래 로직 입니다.

 

class Solution {
  public int[] plusOne(int[] digits) {
    int n = digits.length;

    // move along the input array starting from the end
    for (int idx = n - 1; idx >= 0; --idx) {
      // set all the nines at the end of array to zeros
      if (digits[idx] == 9) {
        digits[idx] = 0;
      }
      // here we have the rightmost not-nine
      else {
        // increase this rightmost not-nine by 1
        digits[idx]++;
        // and the job is done
        return digits;
      }
    }
    // we're here because all the digits are nines
    digits = new int[n + 1];
    digits[0] = 1;
    return digits;
  }
}

 

이 로직은 하나의 for 을 사용했는데요. 그 안에서 아래와 같은 일을 합니다.

- 일단 모든 9을 0으로 바꾼다. 0이 아닌 값이 있으면 1을 더해서 리턴한다.

 

이렇게 되면 위 경우의 수 1번과 2번이 해결 됩니다.

 

모든 숫자가 9인 경우는 for 문 안에 있는 else 가 실행되지 않고 그 아래 코드로 넘어 가는데요.

여기서 배열의 크기를 하나 늘린 새로운 배열을 만들어서 맨 앞에 1을 넣습니다.

 

 

아래 3개가 첫번째 로직 으로 돌린 것이고 위에 3개가 두번째 로직을 돌린 겁니다.

For 루프를 하나밖에 안 쓴 두번째 로직 이 훨씬 빠릅니다.