Leetcode 1354. Construct Target Array With Multiple Sums

문제

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure

let x be the sum of all elements currently in your array.
choose index i, such that 0 <= i < n and set the value of arr at index i to x.
You may repeat this procedure as many times as needed.
Return true if it is possible to construct the target array from arr, otherwise, return false.

정수 n개로 이루어진 배열 target이 주어집니다.

처음에는 길이가 n이고 모든 원소가 1인 배열 arr에서 시작합니다.

다음 과정을 원하는 만큼 반복할 수 있습니다.

1. 현재 배열 arr의 모든 원소의 합을 x라고 합니다.
2. 인덱스 i를 하나 선택합니다. 단, 0 <= i < n입니다.
3. arr[i]의 값을 x로 바꿉니다.

이 과정을 반복해서 arr을 target 배열과 같게 만들 수 있으면 true를 반환하고, 불가능하면 false를 반환하세요.

예시

입력: target = [9, 3, 5]
출력: true

설명:

처음 배열은 arr = [1, 1, 1]입니다.

[1, 1, 1], 합 = 3, 인덱스 1 선택
[1, 3, 1], 합 = 5, 인덱스 2 선택
[1, 3, 5], 합 = 9, 인덱스 0 선택
[9, 3, 5] 완료

따라서 [1, 1, 1]에서 시작해서 target = [9, 3, 5]를 만들 수 있으므로 true를 반환합니다.

제한

$n == target.length$
$1 <= n <= 5 * 10^4$
$1 <= target[i] <= 10^9$

풀이

[3, 5, 9] 로 예시를 들어보자

• 해당 경우에서 가장 늦게 만들어진 수가 뭘까?

  • 9이다!

• 왜냐하면 어떤 값을 만들 때는 현재 배열 전체의 합으로 값을 바꾸기 때문이다.

  • 따라서 마지막에 만들어진 값은 현재 배열에서 가장 큰 값이라고 볼 수 있다.

• 9가 만들어지기 전에는 값들이 어땠을까?

  • [3, 5, 1]!

• 즉 가장 큰 값인 9에서 나머지 값들의 합인 3 + 5를 빼면, 그 자리에 있던 이전 값을 복원할 수 있다.

[3, 5, 17]로 예시를 들어보자

• 이 경우 바로 전 배열은 [3, 5, 9]가 될 것이다!
• 왜냐하면 17이 만들어지기 전, 나머지 값들의 합은 3 + 5 = 8이기 때문이다.
• 따라서 17의 이전 값은 17 - 8 = 9이다.
• 어? 이거 완전 똑같다!
• [3, 5, 17]의 이전 상태는 [3, 5, 9]이고, [3, 5, 9]의 이전 상태는 [3, 5, 1]이 된다.
• 즉 같은 값을 계속 빼는 상황이 반복된다.
• 그러므로 단순히 나머지 값들의 합을 한 번 빼는 것이 아니라, 나머지 연산을 사용해서 여러 번의 뺄셈을 한 번에 처리할 수 있다.

그러니까, 가장 큰 값에 대해 나머지 값들의 합을 나머지 연산 해서 그 값을 넣으면 일종의 역연산이 되겠구나

• 다만

1. 가장 큰 값이 나머지 값들의 합보다 작거나 같은 경우 -> 이전 값이 0 이하가 되므로 절대 역연산이 불가능하기 때문에 False 리턴
2. 나머지 값들의 합이 1인 경우 -> 계속 빼다 보면 언젠가는 가능해지기 때문에 True 리턴

이 두가지는 빠르게 확인할 수 있겠다.

또한 배열의 길이가 1이고, [1] 이 아닌 경우는 미리 빠르게 False를 리턴할 수 있겠다.

최종적으로 하나 더 빼자면, 나머지 값의 합으로 나머지 연산한 결과값이 0인 경우, 1로만 이루어진 배열로 역연산이 불가능하기에 False를 리턴한다.

그래서 어떻게 풀까?

• 가장 큰 값을 계속 트래킹할 수 있어야 한다.
• Maxheap을 쓰자!
• 나는 파이썬을 쓸 것이기에 기본으로 minheap만 있음.
• 따라서 값을 음수로 넣어서 maxheap처럼 사용하자.
• 어차피 전체 합도 계속 필요하므로, maxheap 객체 안에서 현재 합도 같이 관리하자.

코드

from typing import List
from heapq import heapify, heappop, heappush


class MaxHeap:
    def __init__(self, arr: List[int]):
        self.h = [-v for v in arr]
        self.summation = sum(arr)
        heapify(self.h)

    def pop(self):
        target = -heappop(self.h)
        self.summation -= target
        return target

    def push(self, target: int):
        self.summation += target
        heappush(self.h, -target)

    def peek(self):
        return -self.h[0]


class Solution:
    def isPossible(self, target: List[int]) -> bool:
        N = len(target)

        if N == 1 and target[0] != 1:
            return False

        max_h = MaxHeap(target)

        while max_h.peek() != 1:
            largest = max_h.pop()

            if largest <= max_h.summation:
                return False
            elif max_h.summation == 1:
                return True

            largest %= max_h.summation

            if largest == 0:
                return False

            max_h.push(largest)

        return True