448. Find All Numbers Disappeared in an Array

- 원문

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

- 해석

1 ≤ a [i] ≤ n (n은 배열의 크기) 인 정수 배열이 주어지면 일부 요소는 두 번 나타나고 다른 요소는 한 번 나타납니다.

이 배열에 나타나지 않는 [1, n]의 모든 요소를 찾습니다.

여분의 공간없이 O (n) 런타임에서 수행 할 수 있습니까? 반환 된 목록이 추가 공간으로 계산되지 않는다고 가정 할 수 있습니다.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

- 회고

이 문제를 풀때 핵심은 크게 1. 추가 메모리공간을 사용해선 안된다. 2. O(n) 시간복잡도로 수행해야한다. 2가지 경우를 모두 만족해야 한다는게 핵심이었다. 나는 이 2가지를 모두 만족시킬만한 방법이 떠오르지 않았다..ㅋㅋ.. 처음에 생각했던 방법은 DP에서 주로 사용하는 비트마스크를 이용한 메모이제이션을 떠올렸는데 2번인 O(n) 시간복잡도 문제에서 걸리게 되었다. 그리고 계속 생각해나가면서 나도 모르게 추가 변수를 선언하는 실수를 범하고 있었다. 그래서 이를 어떻게 해야 나이스한 방법일지 찾아보니 다음과 같은 방법을 알게 되었다.

- 소스코드

public class Solution {
    public List findDisappearedNumbers(int[] nums) {
        List result = new ArrayList();
        int length = nums.length;
        int val = 0;
        
        // nums[i]에 value-1에 해당하는 index를 바라본다.
        // 만약 해당 index에 해당하는 값을 방문하면 음수, 방문하지 않았으면
        // 양수로 만들어 이 문제를 해결한다.
        // nums[nums[i] - 1] = - nums[nums[i] - 1]
        for(int i = 0; i < length; i++){
            // 해당 i번째 index의 값이 [1...n] 중에서 이미 나왔던 값인 경우 음수로 처리했기 때문에
            // 절대값으로 처리한다.
            val = Math.abs(nums[i]) - 1;
            if(nums[val] > 0){ // [1...n] 중에서 이미 나왔던 값인 경우는 제외
                nums[val] = -nums[val];
            }
        }
        
        for(int i = 0; i < length; i++){
            if(nums[i] > 0){
                result.add(i+1);
            }
        }
        
        return result;
    }
}

위와 같은 소스의 경우 요구사항 1, 2를 모두 만족하기 때문에 가장 최적화된 코드라고 생각한다. 이렇게 배열을 추가로 선언하지 않고 음수로 만들어 방문을 기록하는 방법을 알아두면 매우 유용할 것 같다.