Leetcode 41. First Missing Positive

소스코드

문제

• [41. First Missing Positive]

풀이 (brute-force)

• 순회하면서 HashMap 에 데이터를 마킹한다.
• HashMap 을 처음부터 순회하면서 missing num 을 찾는다.
• 시간복잡도, 공간복잡도 O(n)

    fun firstMissingPositive(nums: IntArray): Int {
        val hashMap = HashMap<Int, Boolean>()

        for (num in nums) {
            if (num > 0) {
                hashMap[num] = true
            }
        }

        var missingNum = 1
        while (hashMap.containsKey(missingNum)) {
            missingNum++
        }

        return missingNum
    }

풀이 ( 공간복잡도 O(1) )

• 상세 풀이 주석
• 전체적인 방향은 기존 nums 를 재활용하는 것
• nums 는 1<= nums.length <= 10의 5승 -> 이 말은 10의 5승을 넘어서는 값이 나올 수 없다는 것
• nums 에 1~10의 5승에 대한 값이 존재하면 0 표시, 범위 밖이라면 -1 표시

   /**
     * 제약 조건을 보면 1<= nums.length <= 10의 5승임
     * 숫자가 연속적으로 나와도 10의 5승 범위를 벗어나는 값이 나올수가 없음
     *
     * 전체 방향은 기존 nums 를 재활용하는 것이다.
     */
    fun firstMissingPositive(nums: IntArray): Int {
        val numsSize = nums.size
        // 범위 이외의 값을 -1 처리
        for (i in nums.indices) {
            if (nums[i] < 1 || numsSize < nums[i]) {
                nums[i] = -1
            }
        }

        // 범위 안의 값이 존재한다면 nums 에 0 으로 표시한다.
        // 예를 들면, [3,4,5] 가 nums 라면 nums[3] = nums[4] = nums[5] = 0 이다.
        // 0 이라는 것은 값이 존재한다는 것
        for (i in nums.indices) {
            marking(nums, nums[i])
        }

        // 순회하면서 nums 가 0 이 아닌 것은 반환한다.
        for (i in nums.indices) {
            if (nums[i] != 0) {
                return i + 1
            }
        }

        // nums 가 전부 채워졌다는건 10의 5승 다음 숫자를 의미
        return numsSize + 1
    }

    /**
     * 순회한 num 이 nums 범위안에 있으면 nums[num-1] = 0 으로 표시
     * ex) num 3 이고, nums[3-1] = 0 이면 3 은 존재하는 숫자라는 의미
     * nums[0] = 0 이면 1은 존재하는 숫자
     */
    fun marking(nums: IntArray, num: Int) {
        if (num > 0) {
            val tmp = nums[num - 1]
            nums[num - 1] = 0
            marking(nums, tmp)  // 중요. 기존에 존재하던 값은 위치를 찾아준다.
        }
    }