[NeetCode/Python] Plus One

코테 스터디는 꾸준히 하면서 문제는 풀었지만 회사일이 좀 바빠 블로그에 업로드를 하지 못했다.

밀린 글들 다 올려야지!

 

문제 링크:

https://neetcode.io/problems/plus-one

NeetCode

 

간단한 수학문제다. 다만 이제 덧셈을 리스트를 이용해 해야한다.

 

 

[내 풀이]

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        result = []
        add = 1
        for i in reversed(digits):
            if i + add < 10:
                result.insert(0, i+add)
                add = 0
            else:
                result.insert(0, 0)
                add = 1

        if add == 1:
            result.insert(0, add)

        return result

 

음... 그냥 직관적으로 풀었다.

일단 덧셈은 뒤에 가장 least significant digit부터 이루어져야 하니, reversed() 를 써서 거꾸로 숫자를 가져왔다.

그리고 1을 더한 후에 올림을 해줄지의 여부는 당연히 10이 되느냐 마냐로 결정할 수 있었고,

10 미만이라면 그냥 1을 더한 수를 넣어주면 된다. 10 이라면 다음 숫자로 1을 넘겨줘야한다. 이를 위해 add라는 변수를 추가했다.

most -> least significant digit 순서대로 리스트가 구성되어 있어야 하기 때문에 append 대신 insert를 사용해서 0 번째에 계속 숫자를 넣어줬다. (stack으로 push 하고 pop한 순서대로 해도 됐을듯)

 

사실 엄청 효율적인 코드는 아니다. reversed 와 insert를 쓴게 특히 마음에 걸리고 쓸데없이 모든 리스트를 순회한게 마음에 걸린다.

사실 list 길이가 100 이하라서 그냥 직관적으로 짰다^^..

 

 

[Solution 코드]

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        one = 1
        i = 0
        digits = digits[::-1]

        while one:
            if i < len(digits):
                if digits[i] == 9:
                    digits[i] = 0
                else:
                    digits[i] += 1
                    one = 0
            else:
                digits.append(one)
                one = 0
            i += 1
        return digits[::-1]

 

reversed 대신 step = -1 을 사용해서 순서를 거꾸로 뒤집었다.

주목할만한 점은 while문을 반복하면서 더이상 '올림'이 필요가 없으면 바로 계산을 끝내게끔 했다! -> !!!

그게 가능했던건 나처럼 새로 result를 만드는게 아닌 digit을 그대로 사용했기 때문이다!

(맞아! 그냥 리스트의 값을 바꾸면되는데 굳이 왜 리스트를 새로 만들었을까..)

 

그리고 나처럼 굳이 더해서 비교하지 않고, 애초에 숫자가 9인지를 확인했다.

나와 비슷한 점은 add와 용도가 똑같은 one이라는 변수를 사용했다는 것.

 

마지막으로 나는 올림이 남으면 리스트에 넣어주는걸 for문 밖에다가 작성했는데 여기서는 while문 안에 깔끔하게 넣었다.

length로 마지막인지 아닌지를 판단한게 똑똑하다 -> !!!

 

역시 마지막에 reversed 대신 step을 사용했다.

 

시간 복잡도

O(n)

-> n은 digits 리스트의 길이