Plus One - LeetCode

Problem

1. input: 정수 배열 digits
2. output: digits을 이어붙인 정수보다 1 큰 정수를 배열(각 자리값)로 리턴
   • 1 <= digits.length <= 100
   • 0 <= digits[i] <= 9
   • digits does not contain any leading 0's.

Idea

digits의 길이가 최대 100이기 때문에, digits을 이어붙여 정수로 변환하는 방법은 불가능하다(정수(int, long)의 범위를 벗어남).

1의 자리부터 각 자리마다 값을 배열로 넣어줘야한다.

Solution

1. 배열을 통해 각 자리마다 값 계산

   • 1의 자리 값에 + 1
   • 10 이상인 경우 pass에 1 저장하고 - 10
   • 해당 값 리턴 배열에 저장
   • 10의 자리 값에 + pass
   • .. 반복

   class Solution {
       fun plusOne(digits: IntArray): Array<Int> {
           val answer = Array<Int>(digits.size + 1) { 0 } // 10을 넘어갈 수 있으므로 여유 한자리
           var idx = answer.size - 1
           var pass = 1 // 10을 넘는 경우 처리용 (원래 값이 +1 해야하므로 초기값 1)
           var value = 0
           while (idx > 0) {
               value = digits[idx - 1]
               value += pass
               pass = 0
               // 10 이상인 경우
               if (value >= 10) {
                   pass = 1
                   value -= 10
               }
               answer[idx] = value
               idx--
           }
           if (pass > 0) answer[idx] = pass
           // 10을 넘지 않은 경우, 여유 한자리 삭제
           return if (answer.first() == 0) answer.sliceArray(1 until answer.size) else answer
       }
   }
   

   시간 복잡도: 배열 순회 = n

   

Point

1. 10 이상인 경우 초과한 값을 저장해줄 변수 하나 설정