Patching Array

문제 번호, 이름: 330. Patching Array

문제 링크: https://leetcode.com/problems/patching-array/description/

날짜: 2024/06/16

상태: 완료!!!

 

이 문제를 고른 이유

리트코드 오늘의문제

문제 보고 처음 든 생각

hard를 연습을 하긴 했어야 했는데 hard가 걸리다니 두렵다

문제 읽는데만 3분. add/patch의 뜻을 잘 모르겠다. 예제는 다 add만 하고 있는 거 같은데 patch는 뭘까

 

풀이 v1

• 소요 시간 48분

Memory Limit Exceeded

(메모리 아니어도 시간복잡도 때문에 타임리밋도 걸렸을 듯)

 

from collections import defaultdict

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        len_num = len(nums)

        existing = set()
        for num in nums:
            copied_existing = [0] + list(existing)
            copied_existing = [x + num for x in copied_existing]
            existing = existing.union(copied_existing)

        not_existing = set([num for num in range(1, n+1)]).difference(existing)

        needed_num_dict = defaultdict(set)
        for not_existing_num in not_existing:
            needed_num_dict[not_existing_num].add(not_existing_num)
            for num in sorted(existing):
                if not_existing_num < num:
                    break
                needed_num_dict[not_existing_num - num].add(not_existing_num)

        answer = 0
        while len(not_existing) > 0:
            answer += 1
            sorted_needed_num = sorted(needed_num_dict.items(), key=lambda x: len(x[1]), reverse=True)
            not_existing = not_existing.difference(sorted_needed_num[0][1])
            del needed_num_dict[sorted_needed_num[0][0]]
            for k in needed_num_dict.keys():
                needed_num_dict[k] = needed_num_dict[k].difference(sorted_needed_num[0][1])

        return answer

 

• 일단 헷갈렸던 add/patch의 개념에 있어서는.. 풀다보니까 patch할거면 무조건 add 하는게 이득이라는 깨달음을 얻었다. patch에 대해서는 고려하지 않기로 했다.
• 풀이가 너무 감이 안 잡혀서 brute force 방식이라면 풀이가 어떻게 될까 떠올려 봤다. 1~n 을 돌면서 각 숫자에 대해 합을 이룰 수 있는 숫자를 완전탐색하면 O(n) x O(2^len) 일 것 같았다. n<2^31, len<10^4 니까 어마어마하다
• 존재하지 않는 숫자들을 iteration 하면서 존재하는 숫자에 몇을 더하면 이 숫자가 나올까? 를 set에 저장하는 방법을 떠올렸다. 그래서 최소한의 부분집합 개수로 전체집합을 만드는 경우를 택해서 그 부분집합 개수를 답으로 리턴하면 될 것 같았다.
  그래서 챗지피티에게 최소한의 부분집합 개수로 전체집합 만드는 경우에 대해 물어봤다. NP 문제라고 했다. greedy로 풀어서 근사해를 구할 수 는 있다고 했다.
• 지피티한테 추가로 질문했다. 특정 조건을 추가했을 때 NP가 아니게 할 수 있냐? 했더니 매트로이드 라는걸 알려줬다. 좀 읽어봤다. 이 문제 조건에 안 맞는 것 같았다. 그냥 공부만 잘 했다.
• 그런데 문제에서 제공된 토픽 분류를 열어봤더니 greedy라고 했다. 엥?
  잘 생각해보니 greedy로 해도 부분집합 개수 잘 구해질 것 같았다.
• 구현을 했다. 구현을 하면서 든 생각인데,
  • '존재하지 않는 숫자들을 iteration' 하는 것부터가 시간복잡도에서 탈락이었다. 존재하지 않는 숫자는 2^31까지 개수가 커질 수 있기 때문이다.
  • 문제에서는 'add/patch 의 수' 를 구하라고 했는데 나는 구체적으로 어떤 숫자가 add되어야 하는지까지 생각을 하고, 구할 수도 있는 풀이를 하고 있었다. 혹시 여기서 구체적인 숫자 구하기를 버리면 최적화가 가능할까?

풀이 v2

• 소요 시간 추가34분

여전히 Memory Limit Exceeded

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        existing_sums = set()
        for num in nums:
            copied_existing_sum = existing_sums.union({0})
            copied_existing_sum = {x + num for x in copied_existing_sum}
            existing_sums = existing_sums.union(copied_existing_sum)

        answer = 0
        idx = 1
        while idx <= n:
            if idx in existing_sums:
                idx += 1
                continue

            existing_sums = existing_sums.union({x + idx for x in existing_sums})
            answer += 1

            idx *= 2

        return answer

 

숫자를 1부터 읽어가며 비어 있는 숫자를 발견하면 그 숫자를 추가한다고 생각했다. 이러면 가장 적은 추가로 가장 많은 종류의 숫자를 만들 수 있다고 생각했다. greedy라는 토픽을 봐서 그게 힌트가 된 것 이긴 하다.

비어 있는 숫자(예를 들어 4)를 발견해서 그 숫자를 추가한다면, 그 앞에까지는(예를 들어 1, 2, 3) 다 채워져 있으니까 그 숫자의 두 배가 되기 전(예를 들어 1,2,3,4,5,6,7) 까지는 굳이 확인할 필요 없이 다 채워질 것이라고 볼 수 있다. 그래서 idx를 두 배 키웠다.

이 코드는 빈 숫자 채우는 부분의 시간복잡도가 O(logn) 이라서 풀이v1 보다는 빠른 것 같아서 일단 v2로 한 번 정리하기로 했다. 근데 existing_sums를 관리하는데 메모리 + 메모리 관리 시간 cost가 꽤 드는 것 같다. 그리고 초기 existing_sums 만드는 데에는 여전히 O(2^len) 시간이 들 것도 같다..

그럼 existing_sums의 관리가 필요 없는 풀이를 만들면 이 두가지 문제를 동시에 해결할 수 있어 보인다 

 

풀이 v3

• 소요 시간: 총 2시간 9분 ㅠㅠ

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        len_num = len(nums)
        num_idx = 0

        answer = 0
        n_idx = 1
        while n_idx <= n:

            if num_idx >= len_num:
                n_idx *= 2
                answer += 1
                continue

            assert nums[num_idx] >= n_idx

            if nums[num_idx] >= n_idx:
                if nums[num_idx] > n_idx:
                    answer += 1
                else:
                    num_idx += 1
                n_idx = n_idx * 2
                while num_idx < len_num and nums[num_idx] < n_idx:
                    n_idx += nums[num_idx]
                    num_idx += 1

        return answer

 

v1과 v2에서는 nums가 sorting 되어있다는 힌트를 이용하지 않았다는 것을 깨달았다

풀이를 말로 설명하기도 어렵다

기본적으로는 살피는 숫자를 2배씩 해 가는데, 2배로 건너뛰는 그 사이에 다른 숫자가 존재한다면 그 숫자를 더해서 2배보다 좀 더 뛰어넘을 수 있도록 했다

마지막엔 어떻게 했는지도 모르겠고 돌려서 틀리면 고치고 틀리면 땜빵하고.. 이렇게 했다 ㅜㅜ

 

남의 설명을 읽어보았다.

방법은 같고, 코드가 좀 더 간결했다

 

이 문제를 풀고 얻은 것

• 끈기..
• 순차적으로 업그레이드된 풀이 (그게 좀 더 빠른 시간안에 이루어졌으면 좋았겠지만)
• https://en.wikipedia.org/wiki/Set_cover_problem 전체집합을 구성하는 최소갯수의 부분집합 구하기는 NP hard 라는 정보

메모

• ㅇ<-<... 코테고수 되고 싶다