[Leetcode] 3354. Make Array Elements Equal to Zero

오늘의 문제는 0과 자연수로 이루어진 배열이 주어지고, 이후 특정 지시대로 움직이며 배열의 모든 원소를 0으로 만들 수 있는지를 판단하는 문제. 시작점에서 왼쪽 또는 오른쪽으로 이동하면서 0이 아닌 숫자를 만나면 -1 을 한 뒤 방향을 바꾼다.

문제에서 하라는 대로 인덱스를 이동해가면서 풀면 엄청나게 시간이 오래 걸리고, 특정 인덱스를 골랐을 때 배열의 좌우 합이 같은지만 보면 된다. 배열의 모든 원소의 합이 홀수인 경우에는 좌우 합이 1 차이나는 지점을 찾으면 된다. 특이하게 시작점과 시작 방향을 같이 정하므로 좌우 합이 정확히 같은 지점은 +2를 해준다(왼쪽+오른쪽).

누적합을 이용해서 쉽게 풀었다.

function countValidSelections(nums: number[]): number {
    const p = [nums[0]]
    for (let i = 1; i < nums.length; i++) {
        p.push(p[i -1] + nums[i])
    }

    const sum = p[p.length - 1]

    let answer = 0

    for (let i = 0; i < p.length; i++) {
        const gap = 2 * p[i] - sum;

        if (nums[i] === 0 && gap >= -1 && gap <= 1) {
            if (gap === 0) {
                answer += 2
            } else {
                answer += 1
            }
        }
    }

    return answer;
};

처음엔 실행시간이 55ms 정도 나와서 줄여보려고 최적화 할 수 있는 부분을 보다가 if 문 안의 조건식을 gap >= -1 && gap <= 1 && nums[i] === 0 에서 nums[i] === 0 && gap >= -1 && gap <= 1 로 바꿨더니 실행시간이 확 줄었다. 역시 조건식이 여러개일 때에는 단락 평가 를 신경써야 한다.