448. Find All Numbers Disappeared in an Array

[soozynn]

내 풀이

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const result = [];
    const set = new Set();

    for (number of nums) {
        if (!set.has(number)) {
            set.add(number);
        }
    }

    for (let i = 1; i <= nums.length; i++) {
        if (!set.has(i)) {
            result.push(i);
        }
    }

    return result;
};

---

Follow up 최적화 풀이

💡 “Could you do it without extra space and in O(n) runtime?” -> 추가 공간을 사용하지 않고.

문제의 핵심

여기서 말하는 **“extra space”**는
_nums 배열 외에 새로운 배열이나 자료구조(Set, Map 등)를 쓰지 말라_는 뜻
즉, nums 배열 자체를 이용해서 풀 수 있는가? 가 핵심.

✅ 최적화 풀이: 제자리 인덱스 마킹 방식

💡 핵심 아이디어
nums 배열의 값은 1~n 사이
이를 이용해서 배열 자체를 표시 도구로 활용할 수 있음
등장한 숫자에 해당하는 인덱스 위치를 음수로 마킹함

✅ 코드 (O(n), 추가 공간 없이)

var findDisappearedNumbers = function(nums) {
    // Step 1: 마킹
    for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]) - 1; // 값에서 인덱스를 구함
        if (nums[index] > 0) {
            nums[index] = -nums[index]; // 음수로 마킹
        }
    }

    // Step 2: 양수인 인덱스는 해당 숫자가 없다는 뜻
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.push(i + 1); // 인덱스 → 숫자 복원
        }
    }

    return result;
};

[soozynn]

이제는 easy 문제를 20분 내에 풀 수 있는 수준이 되어서 다음 주차 부터는 medium 난이도 문제를 주차별로 2문제 이상씩 풀어보려고 한다.