[오늘의 코테 연습장] [LeetCode] 80. Remove Duplicates from Sorted Array II

🔖 문제

• 비내림차순으로 정렬된 정수 배열에서 중복을 일부 제거하여 각 고유한 요소가 최대 두 번 나타나도록 하세요.

• 요소의 상대적인 순서를 유지해야 합니다.

• 중복을 제거한 후 k개의 요소가 남으면, nums의 처음 k개 요소에 최종 결과를 저장해야 합니다.

• k값을 반환하세요.

• 공간복잡도 : O(1)여야합니다.

🔖접근 방식

문제를 보자마자 HashMap을 이용하여 요소와 요소의 등장횟수를 저장해야겠다는 생각이 들었습니다.

1. counts라는 HashMap을 생성하여 각 숫자의 등장 횟수를 저장합니다.
2. k는 nums 배열에서 새로운 요소를 추가할 index를 나타냅니다.
3. for문을 사용하여 입력 배열 nums의 요소를 순회합니다.
4. counts에 num과 num의 등장횟수를 저장합니다.
5. 등장 횟수가 2 이하인 경우, 해당 숫자를 배열(nums)의 k 인덱스 위치에 저장하고 k 값을 1 증가시킵니다.
6. k 값을 반환합니다.

이렇게 k라는 변수를 두고 nums[k] = num으로 한 이유는 문제에서 공간복잡도를 O(1)로 하라고 조건을 제시하였기 때문에, 해당 조건을 지키기위해 그렇게 설계하였습니다.

🔖문제 풀이 코드

import java.util.*;

class Solution {
    public int removeDuplicates(int[] nums) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        int k = 0;
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            //  등장 횟수가 2 이하인 경우 배열에 추가
            if (counts.get(num) <= 2) {
                nums[k] = num;
                k++;
            }
        }

        return k;
    }
}