[Leetcode] 2197. Replace Non-Coprime Numbers in Array

오늘은 최소공배수, 최대공약수를 활용하는 문제가 나왔다. 최대공약수는 유클리드 호제법을 통해 간단하게 얻어낼 수 있고, 최소공배수는 최대공약수를 가지고 쉽게 구할 수 있다. 유클리드 호제법의 시간복잡도는 O(logN) 에 가까우므로 시간복잡도가 발목을 붙잡을 일은 거의 없다고 보면 된다.

인접한 두 수가 서로소인시 반복적으로 확인해야 하므로 스택 자료구조를 활용했다. iterable 한 자료구조를 순회하면서 인접한 원소들을 처리하는데에는 스택을 사용하는 것이 여러모로 좋다. 단, 스택에 넣고 빼는 시점을 정확하게 결정해야 한다.

function replaceNonCoprimes(nums: number[]): number[] {
    const stack = []

    for (let num of nums) {
        while(stack.length > 0 && (gcd(stack[stack.length - 1], num) > 1)) {
            const lastNum = stack.pop()
            const newNum = lcm(lastNum, num)

            num = newNum
        }

        stack.push(num)
    }

    return stack
};

function gcd(a: number, b: number): number {
    if (b === 0) {
        return a
    }

    return gcd(b, a % b)
}

function lcm(a: number, b: number): number {
    return (a * b) / gcd(a, b)
}