LeetCode - 2357. Make Array Zero by Subtracting Equal Amounts

문제가 의미하는 것을 생각하는데 한 10분 정도 걸린 것 같다.

매회마다 array에 있는 가장 작은 수보다 작거나 같은 값 x를 선택한 후, array의 모든 양수인 값에서 x를 빼라는 것은..

작거나 같은 값을 선택하라고 하지만, 최소로 실행하려면 같은 값을 선택해야 한다.

또한, 매회마다 array의 모든 양수에서 x를 빼는데, 이건 결국 매회마다 최소 값들을 제외하는 것과 같은 의미이다.

왜냐하면 매회 최소값을 빼더라도, 그보다 큰 값을 0으로 만들 수는 없기 때문이다.

 

이걸 생각해낼 때 예제에서 주어진 array에 중간 값을 추가했을 때는 어떻게 될지, 더 큰 값을 추가했을 때는 어떻게 될지를 생각해봤다.

[1, 5, 0, 3, 5] -> [0, 4, 0, 2, 4] -> [0, 2, 0, 0, 2] -> [0, 0, 0, 0, 0]

[1, 5, 0, 3, 5, 4] -> [0, 4, 0, 2, 4, 3] -> [0, 2, 0, 0, 2, 1] -> [0, 1, 0, 0, 1, 0] -> [0, 0, 0, 0, 0, 0]

[1, 5, 0, 3, 5, 6] -> [0, 4, 0, 2, 4, 5] -> [0, 2, 0, 0, 2, 3] -> [0, 0, 0, 0, 0, 1] -> [0, 0, 0, 0, 0, 0]

 

이렇게, 결국 매회마다 같은 값이었던 값을 오름차순으로 제거하는 것이다.

즉, 이 연산의 최소 횟수는 서로 다른 element의 개수와 같다.(element != 0)

 

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        unordered_set<int> set_num;
        for (auto i: nums) {
            if (i == 0) continue;
            set_num.insert(i);
        }
        return set_num.size();
    }
};

unordered_set을 사용해서 0이 아닐 경우에 값을 삽입하고, 그 set의 size를 반환했다.

 

Key Idea

문제 푸는 방법 생각.

다른 예제 대입해보기.