LeetCode: 80번 (Remove Duplicates from Sorted Array II) [JAVA]

문제 링크

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Remove Duplicates from Sorted Array II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 현재의 숫자를 나타내는 nowNum, 현재 숫자의 개수를 나타내는 nowNumCount, 바꿔야할 숫자의 인덱스를 담은 changedIndex를 각각 nums 배열의 첫 번째 요소, 1, 1로 초기화
2. nums의 첫 번째 요소를 제외한 그 이후부터 for문을 통해 반복
   1) 만약 현재 요소의 숫자가 nowNum과 동일하다면 ++nowNumCount, 다르다면 nowNum을 해당 숫자로 설정하고 nowNumCount를 1로 초기화
   2) 이후 만약 현재 nowNumCount가 2 이하일 때, changedIndex가 현재 요소 위치보다 앞이라면 숫자 교체를 진행
   3) ++changedIndex
3. 최종 changedIndex 반환

 주어진 nums 배열 속 요소들의 중복이 최대 2개만 존재하도록 새로 정렬을 진행해야 하는 문제이다. 다만 주어진 배열 속 요소들이 애초에 정렬이 되어 있기 때문에, 중복된 숫자들 속 2개를 넘는 숫자들의 처리만 신경쓰면 된다. 일반적으로 해결방법을 생각하며, 처음에는 2개를 넘는 숫자들에 대해서 배열의 뒤로 보내면서, 그 이후 숫자들을 전체적으로 하나씩 땡겨오는 방법을 생각했지만 그런 경우 필요 이상의 연산이 요구되기 때문에 다른 방법이 필요하다.
 해당 문제의 경우 중복된 숫자들의 처리는 신경쓸 필요가 없기 때문에, 해당 숫자들이 다른 숫자로 덮어씌워지거나 해도 상관이 없다. 결국 이후에 올 숫자들로 덮어씌워도 상관이 없기에, 이를 활용하여 2개를 넘는 숫자들을 처리한다. 우선 현재의 숫자를 나타내는 nowNum, 현재 숫자의 개수를 나타내는 nowNumCount, 바꿔야할 숫자의 인덱스를 담은 changedIndex를 각각 nums 배열의 첫 번째 요소, 1, 1로 초기화한다. 그 다음 배열을 for문을 통해 반복을 진행하는데, 만약 현재 위치의 요소가 현재 nowNum과 같다면 nowNumCount를 하나 증가시키고, 다르다면 nowNum을 해당 숫자로 초기화하고 nowNumCount를 1로 바꾼다.
 이후 nowNumCount에 따라 처리를 진행하는데, 현재 숫자 개수가 2 이하인 경우, 만약 현재 요소의 위치보다 changedIndex 숫자 위치가 앞이라면, changedIndex 위치에 있는 숫자는 덮어씌워도 상관없는 숫자이기 때문에 해당 위치를 현재 값으로 덮어씌운다. 별개로 changedIndex는 현재 덮어씌워야할 숫자들의 위치를 나타내는 변수로, 현재 nowNumCount가 2이하인 경우에만 changedIndex를 하나씩 증가시켜 2번의 중복된 숫자들만 지나가도록 한다.
 해당 반복이 완료되면, 해당 배열 속 정렬이 완료된 구간의 개수값을 반환해야 하는데, 이 값이 최종 changedIndex 값과 동일하기 때문에 해당 값을 반환한다.

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int nowNum = nums[0], nowNumCount = 1, changedIndex = 1;//초기값

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nowNum) {//숫자가 같다면 개수 카운트
                ++nowNumCount;
            }else {//다르다면 새롭게 설정
                nowNum = nums[i];
                nowNumCount = 1;
            }

            if (nowNumCount <= 2) {//현재까지의 숫자 개수가 2개 이하인 경우
                if (changedIndex < i){//바꿔야하는 숫자 위치가 지금부터 앞인 경우 숫자 교체 진행
                    nums[changedIndex] = nums[i];
                }
                ++changedIndex;
            }
        }

        return changedIndex;
    }
}

결과