[LeetCode] 80. Remove Duplicates from Sorted Array II

orca·2023년 8월 24일
0

problem

목록 보기
1/28
post-thumbnail

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

개요

  1. 정수 배열 nums가 제공된다. 배열은 오름차순 정렬되어있다.
  2. 동일한 숫자는 최대 두 번까지 나올 수 있다.
    • 두 번 이상 나올 수 없다.
  3. 원본 배열 nums를 수정하고, 수정된 nums 배열의 유효한 길이 k를 반환해라.
    • nums 배열을 수정
    • nums 배열의 인덱스 k-1 이후는 검사하지 않는다.

문제 해결 아이디어

  • nums 배열을 검사하며 동시에 nums 배열을 수정해야 한다.
    ➡️ 당연히 nums 배열은 앞에서부터 순차적으로 수정된다.
  • 동일한 숫자가 두 개 이상 들어갈 수 없다.
    ➡️ 숫자가 들어간 횟수를 카운팅한다.
    ➡️ 새로운 숫자가 등장하면 카운팅 시작한다.

🧐 nums가 어떤 인덱스까지 수정되었는지와 숫자가 들어간 횟수를 카운팅하자

의사 코드

  1. nums가 어떤 인덱스까지 수정되었는지 기록하는 정수 k를 선언한다.
  2. nums를 돈다.
  3. nums의 현재 원소를 직전 원소와 비교한다.
    3-1. 현재 원소가 직전 원소와 값이 다르다.
    3-1-1. count의 값을 초기화 한다.
  4. count가 2보다 작은지 확인한다.
    4-1. count가 2보다 작다.
    4-1-1. nums[k] = 현재 원소
    4-1-2. k의 값을 1 증가시킨다.
    4-1-3. count의 값을 1 증가시킨다.
  5. k를 리턴한다.
k = 0
count = 0
for(i=0 to nums 끝까지){
	if(현재원소 != 직전원소){
    	count = 0
   }
   if(count < 2){
   nums[k] = 현재원소
   k++
   count++
   }
}
return k

결과

전체 코드 github 링크

다른 풀이

public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }

        int index = 2;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] != nums[index - 2]) {
                nums[index] = nums[i];
                index++;
            }
        }

        return index;
    }

nums.length 를 체크해 연산할 필요가 없는 경우 빠르게 리턴했다.
또 나처럼 count 변수를 이용하지 않고도,index-2 와 현재 인덱스를 확인해 동일하지 않은지 체크했다. 덕분에 아주 간결한 코드가 되었다.

0개의 댓글