Remove Duplicates from Sorted Array II - 리트코드

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

평가

결과 : 성공
소요시간 : 6분

설명

입력
오름차순(중복숫자 있음)으로 정렬된 배열

출력
입력된 배열에서 중복을 최대 2개만 남기고 삭제하기
새롭게 정렬된 배열의 크기를 반환하기

아이디어
nums를 순회하면서 이전값이 무엇인지, 몇 번 나왔는지 기록합니다.
2번 넘게 나온 숫자는 정답에 기록하지 않습니다.

수도코드

cnt =0
prev= 불가능한값
answers = 리스트
repeat nums:
  if prev == 지금값:
    cnt++;
    if cnt > 2 : # 더이상 추가되면 안되는 상태
      prev = 지금값;
      continue;

    # 아직 추가되도 되는 상태
    answer.add(지금값)
  
  # 다른 숫자가 나오면(무조건 정답)
  prev = 지금값;
  cnt = 1;
  answer.add(지금값)

정답 코드

시간복잡도를 향상시키기 위해 nowIdx를 사용해서 바로바로 배열을 초기화하도록 만들었습니다.

import java.util.*;

class Solution {
    public int removeDuplicates(int[] nums) {
        int prev = -1000000; // 불가능
        int cnt = 0;
        int nowIdx = 0;
        for(int num: nums) {
            if (num == prev) {
                cnt++;
                // 불가능 case
                if (cnt > 2) {
                    prev = num;
                    continue;
                }

                // 가능
                nums[nowIdx] = num;
            } else { // 숫자가 달라지면 값들 갱신
                prev = num;
                cnt = 1;
                nums[nowIdx] = num;
            }
            nowIdx++;
        }

        return nowIdx;
    }
}