Leetcode 2197. Replace Non-Coprime Numbers in Array

문제

You are given an array of integers nums. Perform the following steps:

1. Find any two adjacent numbers in nums that are non-coprime.
2. If no such numbers are found, stop the process.
3. Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
4. Repeat this process as long as you keep finding two adjacent non-coprime numbers.
5. Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 108.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

배열을 다음 단계를 거쳐 가공하시오

1. 인접한 요소들중 최소공배수가 1보다 큰 요소를 찾는다.
2. 만약 없다면 중단 -> 그대로 리턴
3. 만약 있다면, 해당 두 숫자를 최소공배수로 바꾼다.
4. 1번 절차로 되돌아간다.

해당 가공의 결과로 나올 배열을 리턴하시오

---

예시

[6,4,3,2,7,6,2]

1. 6, 4 합쳐져 12 >> [12, 3, 2, 7, 6, 2]
2. 12, 3 합쳐져 12 >> [12, 2, 7, 6, 2]
3. 12, 2 합쳐져 12 >> [12, 7, 6, 2]
4. 6, 2 합쳐져 6 >> [12, 7, 6]

=> [12, 7, 6]

---

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^5$
• 해당 연산의 중간 과정에서 나오는 결과값들은 절대 10^8을 넘지 않는다.

---

풀이

• Stack을 이용해서 시뮬레이션한다.
• 뒤에 쌓아나가면서 while로 검사해서 LCM으로 채워넣기

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        s = []

        for num in nums:
            if not s:
                s.append(num)
                continue

            while s:
                g = gcd(s[-1], num)
                if g > 1:
                    v = s.pop()
                    num = v * num // g
                else:
                    break

            s.append(num)

        return s