#26 Remove Duplicates from Sorted Array

전우재·2023년 8월 24일
0

leetcode

목록 보기
3/21

문제링크 - https://leetcode.com/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150

문제 분석

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.(nums는 오름차순으로 정렬되어야 함.)
    입력받은 배열에서 중복되더라도 값 하나만 앞으로 당겨서 정렬시켜야 함.

문제 해결

문제 해결 로직

중복을 제거하는 방법으로 Set이 처음 떠올랐다.

  1. int array nums을 입력받는다.
  2. array의 중복을 제거할 수 있는 Map으로 변경한다.
  3. List로 만들어 오름차순 정렬한다.
  4. 해당 List 크기만큼 array의 앞부터 값을 변경한다.
  5. List의 크기를 반복한다.

코드 작성

class Solution {
  public int removeDuplicates(int[] nums) {
    // set으로 변경하여 유일한 값 구하기
    Set<Integer> integerSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());

    // Set을 오름차순으로 정렬한 리스트 생성
    List<Integer> sortedList = new ArrayList<>(integerSet);
    Collections.sort(sortedList);

    // 유일하며 오름차순으로 정렬된 값을 array 앞부터 넣기
    int index = 0;
    for(Integer integerValue : sortedList){
      nums[index] = integerValue;
      index++;
    }

    return sortedList.size();
  }
}

회고

  • 너무 많은 생성을 하게 되면서 시간 복잡도와 메모리가 많이 소모되었다.
  • 특히 시간 복잡도의 경우 Set과 List를 생성하는데 각각 O(n)이 걸리고 배열에 넣을때도 O(n)이 걸린다.

0개의 댓글

관련 채용 정보