[LeetCode] 66.Plus One (Python)

Problem

 

Solution

string

1자리수 integer가 포함된 list 가 주어지고 이를 숫자로 변환 후 +1한 digit의 자리수를 list에 담아서 반환하는 문제.

string -> int +1 -> string -> int 로 변환해서 풀었다.

다른 사람 풀이를 보니 대부분 이렇게 푼듯

 

더 효율적인 코드는 아래와 같다.

def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):	#n-1 부터 뒤에서 앞으로 반복한다. 즉 마지막 숫자부터 시작
            if digits[i] < 9:
                digits[i] += 1	#현재 숫자가 9보다 작으면 +1하고 종료
                return digits
            digits[i] = 0	#현재 숫자가 9이면 0으로 업뎃해주고
        return [1] + digits	#한자리수 올라가니 앞에 1을 더해주고 return

• 시간 복잡도는 digits 길이만큼 수행되므로 O(N)
• 공간 복잡도는 digits 리스트를 직접 수정하는 방식이므로 O(1)이다.

Code

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        converted = ''
        answer = []
        for num in digits:
            converted += str(num)

        largerNum = int(converted) + 1

        strNum = str(largerNum)
        for i in range(len(strNum)):
            answer.append(int(strNum[i]))
        return answer

 

Complexity

Time Complexity

문자열 변환, 정수로 변환 후 덧셈, 결과 문자열을 다시 리스트로 변환

전체 시간 복잡도는 O(N)

 

Space Complexity

converted, strNum, answer 변수와 리스트를 사용하므로

전체 공간 복잡도는 O(N)