[Leetcode] 2221. Find Triangular Sum of an Array

0~9 사이의 수로 이루어진 정수의 배열이 있고, 두 정수의 합을 새로운 배열에 담아가면서 최종적으로 나오는 값을 구하는 문제. 문제를 푸는 것 자체는 어렵지 않지만 제약조건을 크게 둬서 멍청하게 짜면 시간초과가 뜨는 유형의 문제이다.

Step1. 멍청풀이

머릿속에서 떠오른 가장 간단한 방법은 재귀함수. 새로운 배열은 reduce 를 통해 간단하게 만들 수 있다.

function triangularSum(nums: number[]): number {
    if (nums.length === 1) {
        return nums[0]
    }

    const newNums = nums.reduce((acc, cur, index) => {
        if (index === 0) {
            acc.push(cur)
            return acc
        }

        const num = acc.pop()
        acc.push((num + cur) % 10)

        if (index !== nums.length - 1) {
            acc.push(cur)
        }
        return acc
    }, [])

    return triangularSum(newNums)
};

제출을 해봤는데 다행히 시간초과가 나지 않고 통과했으나 100명 중 100등으로 들어온 것 같은 그래프를 보여준다...

Step2. 멍청풀이 2

원래 주어지는 nums 배열을 가지고 index 를 하나씩 전진시켜가면서 nums.push((nums[i] + nums[i + 1]) % 10) 을 해줬다. 배열의 끝에 다다랐다면 마지막 값을 출력하면 끝. 배열의 끝 마다 건너뛰어야하니까 인덱싱 처리도 제대로 해줬다.

function triangularSum(nums: number[]): number {
    let currentLength = nums.length
    let i = 0

    while(i < nums.length - 1) {
        nums.push((nums[i] + nums[i + 1]) % 10)

        if (i + 1 === currentLength - 1) {
            currentLength = nums.length
            i += 1
        }

        i += 1
    }

    return nums[nums.length - 1]
};

전혀.. 달라진 것이 없다...? 오히려 메모리는 메모리대로 더 잡아먹고 실행시간도 줄이지 못했다..

Step3. 똑똑풀이

다시 한 번 고민을 해봤다. 바로 위의 솔루션에서는 .push()가 계속 일어나고 배열의 길이를 계속 가져와서 업데이트 하는 부분이 시간이 오래 걸리지 않을까 싶었다. 그리고 문득 생각난 것이 이 문제에서는 삼각합을 구하기 때문에 배열의 길이가 계속 줄어든다는 것. 굳이 배열의 길이를 늘려 공간을 많이 차지할 필요가 없었다.

원래의 배열의 원소를 대체하는 방법으로 돌렸다. 어차피 i + 1 은 새로 만드는 배열의 길이 바깥으로 나가지 않는 다는 것을 보장하기만 하면 문제없다.

function triangularSum(nums: number[]): number {
    let n = nums.length;

    while (n > 1) {
        for (let i = 0; i < n - 1; i++) {
            nums[i] = (nums[i] + nums[i + 1]) % 10;
        }
        
        n--; 
    }

    return nums[0];
};

깔끔하게 상위 1퍼센트로 통과했다. 와! 1등급!!