[ Top Interview 150 ] 26. Remove Duplicates from Sorted Array

문제

26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

• Input : 중복이 존재하는 오름차순으로 정렬된 배열 제공
• Output : 제공된 배열을 맨 앞부터 채워서 중복 없는 오름차순 배열로 변형
  • 최종적으로 정렬된 원소의 개수를 return

문제 풀이 전략

• 27. Remove Element 모범 답안 참고 하였음
• 선별이 완료된 원소의 위치를 가리키는 answerIndex를 설정
• nums를 순회하면서 answerIndex에 있는 원소보다 큰 경우
  • 해당 원소를 선별이 완료된 원소 위치로 이동함

1차 작성

class Solution {
    public int removeDuplicates(int[] nums) {
        int answerIndex = 0;

        for (int index = 1; index < nums.length; index++) {
            if (nums[answerIndex] < nums[index]) {
                answerIndex++;
                nums[answerIndex] = nums[index];
            }
        }

        return answerIndex + 1;
    }
}

2차 작성 (enhanced for 문 이용)

class Solution {
    public int removeDuplicates(int[] nums) {
        int answerIndex = 0;

        for (int num : nums) {
            if (nums[answerIndex] < num) {
                answerIndex++;
                nums[answerIndex] = num;
            }
        }

        return answerIndex + 1;
    }
}

enhanced for 문

• enhanced for 문

  • Enhanced for-loop의 경우에는 내부적으로 Iterable 인터페이스를 구현한 객체만 사용할 수 있다.
  • 내부적으로 iterable 인터페이스 객체를 만들고 나서, 반복문을 순회한다.
  • 성능 차이는 크지 않으나 위의 경우에는 내부 알고리즘이 간단하므로 백분위에서는 차이가 날 수 있다.
  • enhanced for 문을 사용하면 시각적으로 보기 용이하므로 비즈니스 코드에서는 최대한 사용하는 것을 추천한다.

• 내부적인 코드

  // iterable() 메서드로 iterable 인터페이스 객체 반환
  Iterator iter = list.iterator();
  
  while(iter.hasNext()){ // 순회할 객체가 남아있다면
      Integer num = (Integer)iter.next(); // 다음 객체 가져옴
      //...
  }

• 루프문 비교

  for-loop	Enhanced for-loop
  역순 정렬 가능, 인덱스를 원하는 대로 늘릴 수 있음.	항상 인덱스는 1씩 증가함
  loop 동작 중 내부 요소 변경 가능	loop 동작 중 내부 요소 변경 불가

• 참고 자료