[PS] 같은 수의 뉴런

문제

You are given a neural network with n layers. Each layer has a number of neurons represented by an array layer[], where layer[i] is the number of neurons in the i-th layer.

The network undergoes updates in a sequence of generations. In each generation, you are allowed to increase the number of neurons in at most one layer, according to the following rules:

In odd-numbered generations (1st, 3rd, 5th, ...), you can add 1 neuron to a single layer.
In even-numbered generations (2nd, 4th, 6th, ...), you can add 2 neurons to a single layer.
It is also allowed to skip a generation and apply no changes to any layer.

Your goal is to determine the minimum number of generations required to make all layers have the same number of neurons.

예시

Input: layer = [1, 1, 2, 4]
Output: 6
Explanation:
A possible sequence of generations:

Generation	Operation (Add to Layer)	Resulting Layers
1 (odd)	+1 to layer 0	[2, 1, 2, 4]
2 (even)	+2 to layer 0	[4, 1, 2, 4]
3 (odd)	+1 to layer 1	[4, 2, 2, 4]
4 (even)	+2 to layer 1	[4, 4, 2, 4]
5 (odd)	skip	[4, 4, 2, 4]
6 (even)	+2 to layer 2	[4, 4, 4, 4] ✅

조건

• 1 ≤ n ≤ 10⁵
• 1 ≤ layer[i] ≤ 10⁹
• You may skip a generation (do nothing).

답

최댓값을 구한 뒤, 나머지 계층에서 최댓값이 되기 위해 필요한 뉴런의 수를 계산합니다.

 

한번에 1 혹은 2만큼 증가가 가능하기 때문에, 계산한 뉴런의 수를 1과 2 단위로 분리(decomposing)합니다.

 

이후 1과 2의 개수가 동일하거나, 1의 개수가 하나 더 많아질 때 까지 수를 조절합니다.

 

2를 두 개의 1로 분해할 수도 있고, 아무 행동을 취하지 않는 세대를 추가해 2 또는 1을 추가할 수 있습니다.

function findMinGen(layer) {
    const maxNum = Math.max(...layer);
    let ones = 0;
    let twos = 0;

    for (let i = 0; i < layer.length; i++) {
        const diff = maxNum - layer[i];
        ones += diff % 2;
        twos += Math.floor(diff / 2);
    }

    while (ones !== twos) {
        if (twos - ones === 1) {
            ones += 1;
        } else if (ones < twos) {
            ones += 2;
            twos -= 1;
        } else {
            twos += 1;
        }
    }

    return ones + twos;
}

시간 복잡도 : O(n)

공간 복잡도 : O(1)