LeetCode #1981 Minimize the Difference Between Target and Chosen Elements

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1981. Minimize the Difference Between Target and Chosen Elements

문제 풀이

각 행의 원소 1개씩을 반드시 선택하여 선택한 원소들의 합이 target과 차이가 최소가 되는 값을 구해야 한다. DFS로 풀었난데 TLE가 나서 풀이를 보니 dfs까지 갈 필요는 없고 매 행을 탐색할 때마다 이전 행의 합들을 받아서 현재 행의 원소들에 더한 뒤 마지막에 확인해가며 리턴해야 한다. 그런데 이 방식도 완전 탐색에 가까워 챌린지에서만 통과되고 그 이후엔 TLE가 출력되었다고 한다. 따라서 원소합 집합에 넣을 때 필터 기준을 잘 생각해야 한다.

우선 각 행의 최솟값들을 더한 값을 전체 선택 결과 중 가장 작은 값으로 이 값보다 target이 작으면 앞으로 더 큰 값밖에 존재하지 않아 차이를 리턴하면 된다. 그리고 이 기준을 통과하면 최소한 최소합은 target보다 작음을 알 수 있다.

각 행에서 원소를 더해 집합에 넣을 때마다 넣는 기준을 설정해야 한다. 그렇지 않으면 완전탐색과 다를 바 없기 때문이다. 우선 기준은 target - min_sum으로 하되 이전 합과 현재 항의 합에서 target을 뺀 결과가 target - min_sum보다 크면 더 탐색할 필요가 없으므로 해당 경우를 제외하고 나머지에 대해서는 합집합에 넣어 다음 행으로 보내주면 되겠다.

• 각 행의 최솟값을 더한 최소합 min_sum이 target보다 크면 차이 리턴
• 매 행을 탐색할 때마다 이전 합집합의 원소와 현재 행의 원소를 더한 값이 x + i - target > target - min_sum인 경우를 제외해야 하므로 x + i <= 2 * target - min_sum인 경우에만 합집합에 삽입한다.
• 마지막까지 탐색을 진행하여 생성된 집합에 대해 target과의 차이가 가장 작은 경우를 리턴한다.

python 코드

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        min_sum = 0
        for row in mat:
            min_sum += min(row)
        if min_sum >= target:
            return min_sum - target
        nums = {0}
        for row in mat:
            nums = {x + i for x in row for i in nums if x + i <= 2 * target - min_sum}
        return min(abs(x - target) for x in nums)