[C++] LeetCode - Remove Duplicates from Sorted Array (Hash Map)

이번에는 Remove Duplicates from Sorted Array 문제를 다뤄봤습니다. 저는 Hash Map을 활용하여, 이게 중복된 값인지 아닌지 여부를 확인하는 식으로 진행했습니다.

---

문제 정의

---

접근 방법

• while loop을 통해 원소 하나하나씩 보면서, 해쉬 맵에 저장된 형태라면 중복된 값이므로 pass. 저장되지 않았다면 중복되지 않았으므로 그대로 유지합니다.
• 중복일 경우, 제공된 벡터 값에 -101을 넣어 알 수 있게 합니다. 마지막에 for 문을 통해 -101이 아닌 값들만 가져옵니다.

---

결과

• Runtime: 12 ms, faster than 66.91% of C++ online submissions for Remove Duplicates from Sorted Array.
• Memory Usage: 19 MB, less than 5.40% of C++ online submissions for Remove Duplicates from Sorted Array.

---

코드

---

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        
        int cnt = 0;
        unordered_map<int, int> um;
        
        if (nums.size() == 0) {
            return 0;
        }
        
        while(cnt < nums.size()) {
            if (um[nums[cnt]] > 0) {
                // already exists
                nums[cnt] = -101;
            } else {
                um[nums[cnt]]++;
            } 
            
            cnt++;
        }
        
        
        int ch=0;
        for (auto z : nums) {
            if (z != -101) {
                nums[ch] = z;
                ch++;
            }
        }
        
        
        return ch;
    }
};

---