[Top Interview Questions] 66. Plus One

정답)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # 1의 자리에 1을 더함
        digits[-1] += 1
        
        # digits의 0번째 정수 제외 만약 i번째 정수가 10이면
        # 0으로 바꿔주고 [i-1]에 더함
        for i in range(len(digits)-1, 0, -1):
            if digits[i] == 10:
                digits[i] = 0
                digits[i-1] += 1
        
        # 만약 0번째 정수가 10이면 0으로 바꾸고
        # 0번째 정수에 1을 새롭게 추가
        if digits[0] == 10:
            digits[0] = 0
            digits.insert(0, 1)
        
        return digits

문제)

주어진 리스트 digits는 정수가 자릿값에 따라 놓인 리스트입니다. 정수의 자릿수는 큰 숫자부터 작은 숫자로 왼쪽에서부터 오른쪽으로 정렬되어 있습니다. 정수의 맨 앞에는 0이 존재하지 않습니다.

 

주어진 정수에 1을 더하고 그 정수의 배열을 리턴하시오.

 

예시 1)

digits = [1, 2, 3]

output = [1, 2, 4]

1의 자릿수인 3에 1을 더해 123이 124가 되었습니다.

 

예시 2)

digits = [4, 3, 2, 1]

output = [4, 3, 2, 2]

1의 자릿수인 1에 1을 더해 4321이 4322가 되었습니다.

 

예시 3)

digits = [9]

output = [1, 0]

1의 자릿수인 9에 1을 더해 10이 되었습니다. 하지만 배열의 원소는 자릿수를 나타내기 때문에

[10]이 아닌 [1, 0]이 되었습니다.

 

제한)

• 1 <= digits의 길이 <= 100
• 0 <= digits[i] <= 9
• digits의 맨 앞은 0이 되어서는 안 됩니다.

풀이)

기본원리)

평소처럼 정수에 1을 더하듯 digits의 맨 뒤 숫자 digits[-1]에 1을 더해줍니다.

 

그리고 digits의 맨 뒤부터 1번째 숫자까지 10이 존재한다면 0으로 바꿔주고 다음 숫자에 1을 더해줍니다.

 

1번째 숫자까지 확인했다면 0번째 숫자를 확인해 줍니다.

만약 0번째 숫자도 10이라면 0으로 바꾸고 배열의 맨 앞에 1을 추가해 줍니다.

 

digits를 리턴합니다.

1의 자릿수에 1을 더하기)

어떤 정수에 1을 더한다는 것은 그 정수의 1의 자릿수에 1을 더하는 것이죠.

 

그 원리에 충실히 따라 1을 더해줍시다.

digits의 1의 자릿수는 digits의 배열의 맨 뒤입니다. digits의 맨 뒤 원소는 -1번째 원소죠?

 

그러므로 digits[-1]에 1을 더해줍니다.

 

def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1

digits에 10이 존재한다면?)

digits 배열은 각 원소에 자릿수가 배치되어 있습니다.

그러므로 제한에도 적혀있듯 각 원소는 0부터 9로 이루어져 있습니다.

 

만약 1을 더했다가 그 자릿수가 10이 되었다면 그 자릿수는 0이 되어야 하고 그 위의 자릿수가 1이 더해져야 합니다.

 

1의 자릿수에 1을 더했을 때 10이 된다면 10을 빼주고 그 다음 자릿수에 1을 더해줘 업데이트합니다.

그러므로 -1번째부터 1번째 원소까지 (오른쪽에서부터 왼쪽으로) 10이 존재하는지 확인하고 있다면 0으로 바꿔주고 그다음 자릿수의 숫자를 업데이트해줍시다.

 

0번째 원소를 확인하지 않는 이유는 0번째 원소가 마지막 원소기 때문에 그다음 자릿수의 원소가 존재하지 않습니다.

그러므로 digits[i-1]이 제대로 작동되지 않습니다.

 

def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1

        for i in range(len(digits)-1, 0, -1):
            if digits[i] == 10:
                digits[i] = 0
                digits[i-1] += 1

0번째 원소)

만약 숫자가 -1번째 원소부터 계속 업데이트돼서 0번째 원소마저 10이 된다면 이 숫자도 업데이트해줘야 합니다.

그래서 0번째 숫자를 0으로 바꿔주면 그다음 자릿수에 1을 더해줘야 하지만 그다음 자릿수가 존재하지 않습니다.

 

어떻게 하면 digits의 맨 앞에 새로운 자릿수 1을 추가해 줄 수 있을까요?

 

digits의 현재 존재하는 모든 원소들을 오른쪽으로 한 칸씩 당겨주면 0번째 원소는 빈 자리가 됩니다.

여기에 1을 추가하는거죠.

 

리스트의 insert() 메서드

이렇게 digits의 맨 앞에 추가해 주는 간단한  방법 중 하나는 리스트의 메서드 insert(i, x)을 사용하는 것입니다.

이 메서드는 i번째 자리부터 맨 뒤까지의 원소들을 한 칸씩 뒤로 당겨주고 i번째 자리에 x를 추가해 줍니다.

 

그렇게 모든 자릿수가 업데이트되면 digits를 리턴해줍시다.

 

def plusOne(self, digits: List[int]) -> List[int]:
        digits[-1] += 1

        for i in range(len(digits)-1, 0, -1):
            if digits[i] == 10:
                digits[i] = 0
                digits[i-1] += 1
        
        if digits[0] == 10:
            digits[0] = 0
            digits.insert(0, 1)
        
        return digits

디버깅)

digits = [9, 9, 9]

 

digits = [9, 9, 10]

 

(i=2)

digits = [9, 9, 0]

digits = [9, 10, 0]

 

(i=1)

digits = [9, 10, 0]

digits = [10, 0, 0]

 

digits = [0, 0, 0]

digits = [1, 0, 0, 0]

 

return [1, 0, 0, 0]

 

 

사실 되게 간단하게 푸는 방법이 있습니다. 빈 문자열에 왼쪽에서부터 오른쪽으로 원소들을 추가하고 그 문자열을 정수로 바꿔줍니다. 그리고 그 정수에 1을 더하고 다시 문자열로 바꿔준 후 순서대로 리스트에 추가하는 것이죠. 이게 가능한 이유는 문자열 또한 선형검색이 가능하기 때문입니다.

 

하지만 그렇게 풀지 않은 이유는 너무 날먹(?) 같기도 하고 다른 방식으로 풀어보고 싶어서 이렇게 풀어봤습니다. 사실 최대 관건은 맨 앞에 1을 어떻게 추가하는가 같은데 insert() 메서드를 알면 쉽게 풀었겠죠??

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)

 

참고자료:

달레 블로그