.leetcode(448. Find All Numbers Disappeared in an Array)

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

 

1. 2022/04/27 시도

소요시간: 30분

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        
        // remove duplicates
        int end = 1;
        int prev = nums[0];
        for (int i=1; i<nums.length; i++) {
            if (prev == nums[i]) {
                continue;
            }
            nums[end++] = nums[i];
            prev = nums[i];
        }
        
        // set position
        for (int i=end-1; i>=0; i--) {
            nums[nums[i]-1] = nums[i];
        }
        
        // get missing number
        List<Integer> ret = new ArrayList<>();
        for (int i=0; i<nums.length; i++) {
            if (nums[i] != i+1) {
                ret.add(i+1);
            }
        }

        return ret;
    }
}

풀이 접근 과정

먼저 정렬을 한다. 그리고 중복된 것을 제거하도록 배열을 수정한다.

각 요소가 원래 위치에 위치할 수 있게 포지션을 세팅한다.
ex) 3이면 배열의 2번쨰에 위치하도록 변경

순서대로 읽으면서 위치에 제대로 된 숫자가 있는지 확인한다.

 

느낀점

• 간단한 문제인데 처음에 너무 쉽게 접근하려다보니 오히려 돌아갔다. 위에 풀이는 사실 정렬이 들어갔으니 아무리 빨라도 O(nlogN)이다. 다른 풀이에서는 O(n)으로 풀 수 있다.
• 30분도 오래걸렸다고 생각했는데 처음풀 떄, 55분걸렸떤거 보니 더 나아진거 같긴 하다.
• 아래는 솔루션에서 나온 내용이다. 숫자의 음수/양수를 이용한 방문 여부를 표시하는 방식이다. 기발하다.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        
        for (int i=0; i<nums.length; i++) {
            int newIndex = Math.abs(nums[i]) - 1;
            
            if (nums[newIndex] > 0) {
                nums[newIndex] *= -1;
            }
        }
        
        List<Integer> ret = new ArrayList<>();
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > 0) {
                ret.add(i+1);
            }
        }
        return ret;
    }
}

---

1. 2021/01/03 시도

소요시간: 55분

#공간을 O(1)로 사용해보려고 노력한 풀이(더 효율적인 풀이는 아래)
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);

        moveDuplicates(nums);

        List<Integer> ret = new ArrayList<>();
        int addindex = 0;
        for(int i=0; i<nums.length;i++) {
            if (nums[i-addindex] != (i+1)) {
                ret.add(i+1);
                addindex++;
            }
        }

        return ret;
    }

    private void moveDuplicates(int[] nums) {
        int addindex = 0;
        for(int i=0; i<nums.length; i++) {
            nums[i-addindex] = nums[i];
            if (i < nums.length-1 && nums[i] == nums[i+1]) {
                addindex++;
            } 
        }
    }
}

#HashSet을 이용한 풀이 << 이건 공간을 O(n)으로 쓴다.
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {

        Set<Integer> box = new HashSet<>();
        for (int i=0; i<nums.length; i++) {
            box.add(nums[i]);
        }

        List<Integer> ret = new ArrayList<>();
        for (int i=0; i<nums.length; i++) {
            if (!(box.contains(i+1))) {
                ret.add(i+1);
            }
        }

        return ret;
    }
}

풀이 접근 과정

정열의 방식

해쉬셋을 이용한 방식

 

느낀점

• 정렬하고 겹치는걸 뒤로 보내고 마지막에는 순서를 비교해보는 로직이었다. 저번에 풀었던 MoveZeros를 활용해보는게 무엇보다 재밌는 포인트였다. 그때는 0을 뒤로 보내는거였는데 응용해서 겹치는걸 뒤로 보내는 코드를 만들어보았다.
• 솔루션에 나온 부호를 이용한 풀이는 정말 멋있었다. 제한된 공간에서 이용할 수 있는게 순서말고도 부호라는 특성 즉 토글되는 특성을 이용할 수 있구나 싶었다. 기존에 배운 XOR를 먼저 떠올리긴 했는데 실제로 적용이 어렵고 요소를 여러개 찾아내는것이라 안맞았는데 이렇게 부호를 이용하는 방법도 고려해보면 아주 재밌다.

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형