[LeetCode] Plus One

문제 링크

Can you solve this real interview question? Plus One - You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits. Example 1: Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4]. Example 2: Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. Incrementing by one gives 4321 + 1 = 4322. Thus, the result should be [4,3,2,2]. Example 3: Input: digits = [9] Output: [1,0] Explanation: The array represents the integer 9. Incrementing by one gives 9 + 1 = 10. Thus, the result should be [1,0]. Constraints: * 1 <= digits.length <= 100 * 0 <= digits[i] <= 9 * digits does not contain any leading 0's.

https://leetcode.com/problems/plus-one/description/

문제 요구 조건

정수 배열을 인자로 받게되요.

정수 배열을 각자리로 이루어진 숫자라고 생각하고 1을 더한 수의 배열을 다시 만들어야 해요

예) [1,2,3,4] ⇒ [1,2,3,5]

저의 문제 풀이

결론적으로 해당 시간을 넘겨서 풀게 되었네요. 첫 번재 방식과 두 번째 방식이 조금 다른데, 하나씩 설명해볼게요.

첫 번째 시도

첫 번째 시도한 방법

JavaScript

var plusOne = function (digits) {
    let finalArray = [];
    const joinedDigits = digits.join().replaceAll(',', "");
    console.log(joinedDigits);

    const parsed = parseInt(joinedDigits);
     console.log(parsed);

    const targetNum = parsed + 1;
    const splitted = targetNum.toString();

    for (let i = 0; i < splitted.length; i++) {
        const num = parseInt(splitted[i]);
        finalArray.push(num);
    }

    console.log(finalArray);
    return finalArray;
};

첫 번째 시도한 방법에서는 JavaScript문서를 참고해서, 필요한 메소드를 적극 활용했어요. (코딩 테스트에서 공식문서 참조할 기회는 대게 다 주더라구요!) 그래서 다음과 같이 풀어보았어요.

기존 배열을 join()함수로 합치고, ‘,’ 쉼표를 다 제거하는 replaceAll()함수를 사용했어요.

그래고 해당 문자열을 parseInt()함수를 사용해서 정수로 변환했어요.

그리고 1을 더하고, 다시 문자열로 만들었어요.

string은 인덱스 접근이 가능하니 순회하면서 정수를 변환해서 finalArray에 추가하고 반환했어요.

첫 번째 방법의 문제점

다른 테스트 케이스는 통과했지만, 너무 큰 숫자가 나오면 이 코드는 작동하지 못했어요.

너무 큰 숫자가 할당이 되면, 마지막 인덱스의 숫자들이 0이 되어버리는 현상이 발생했어요.BigInt로 따로 할당하고 해볼까 생각이 들었지만, BigInt는 너무 큰 숫자에 n이 붙어서, 로직이 너무 복잡해 질것 같았어요. 그러다 두 번째 방법을 생각해보게 되었어요.

두 번째 시도

두 번째 시도에는 어차피 각 정수 배열로 반환해야된다면, 1을 더해서 10이 되는 경우를 각각 배열의 요소를 따로 다루어 보자는 아이디어가 떠올랐어요.

두 번째 시도

JavaScript

var plusOne = function (digits) {
    const last = digits.length - 1;
    digits[last] += 1

    for (let i = 0; i <= last; i++) {
        if (digits[0] === 10) {
            digits[0] = 0
            digits.unshift(1)
        }
        if (digits[last - i] === 10) {
            digits[last - i] = 0
            digits[last - (i + 1)] += 1
        }
    }

    console.log(digits)
    return digits
};

두 번째 시도의 과정의 다음과 같아요.

마지막 인덱스를 정의하고, 마지막 인덱스 숫자에 일단 1을 더해요

그리고 각 배열의 요소를 순회하는 for문을 만들어서 i 인덱스가 커질수록 뒤에서 부터 순회할 수 있게 했어요.

그래서 각 숫자가 10이 되면 앞숫자에 1을 더하고 다음 인덱스로 넘어가게 되었어요.

그리고 마지막 인덱스 digits[0]에서 10일 경우가 생긴다면, javsScript 함수의 unshift(1)함수를 사용했어요. unshift함수는 배열에 첫 부분에 요소를 삽입하는 함수에요.

결과

테스트는 통과했지만, 성능면에서는 하위 3%에 속하는 해결방식이었어요.

그럼 다른 분들은 어떻게 했을까요? 최고의 성능을 낸 풀이만 알아보도록 할게요.

최고의 성능을 낸 문제풀이

로직 자체는 비슷하지만 몇가지 로직의 배치로 인해서 성능을 한 층 끌어올릴 수 있다는 걸 깨닫게 해준 풀이에요.

최고의 성능 풀이

JavaScript

var plusOne = function(arr) {
    for(let i = arr.length - 1; i >= 0; i--) {
        if(arr[i] + 1 !== 10) {
            arr[i] += 1;
            return arr;
        }
        arr[i] = 0;
        if(i === 0) {
            arr.unshift(1);
            return arr;
        }
    }
};

제가 이 풀이를 보고 판단한 차이점은 아래와 같아요.

일단 제가 했던 방식은 인덱스가 커질수록 거꾸로 순회할수 있는 로직이었는데, 이 풀이는 직관적으로 바로 뒤에서 부터 순회하도록 했네요.

그리고 더 이상 덧셈 올림이 필요하지 않은 상황이 되면 반복문을 빨리 종료할 수 있도록 했어요. 반면에 제 코드는 항상 처음부터 끝까지 순회해야했어요.

느낀점

가장 중요하게 느낀 차이점을 말한다면, 함수 진행이 중간에 종료될 수 있다면 재빨리 종료시키는 방향으로 코드를 작성해야된다는 사소할지 모르지만 성능상 4배이상의 결과를 만들어 낼 수 있다는 것을 배웠네요 🙂