LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정렬되지 않은 정수 배열 nums
2. output: nums에 없는 가장 작은 양의 정수 리턴
3. 시간 복잡도 제한: O(n)
   • 1 <= nums.length <= 10^5
   • 2^31 <= nums[i] <= 2^31 - 1

Idea

O(n)안에 해결하려면 배열 순회만 가능하다는 뜻이다.

처음 생각한 것은 가능한 nums의 범위만큼 배열을 만들고 Array<Int>(Int.MAX_VALUE) nums에서 양의 정수 값들을 해당 index에 넣어주고 없는 값을 확인하는 것이었다. → 메모리 초과

메모리 초과를 피하기 위해 배열대신 Map을 사용하였고 통과했다. → Sol1

Sol1을 발전시키고 싶었으나 도저히 생각이 나지 않았고, 다른 사람의 풀이를 보던중 ‘Cyclic Sort’에 대해 알게되었다. → Sol2

Sol2의 점수가 Sol1보다 높게 나왔고, Cyclic Sort라는 말이 그럴듯해 보이지만, 결국 둘이 동작 원리와 시간복잡도는 똑같다. 그럼 어디서 차이가 났을까?

또다시 HashMap의 쓰고 읽는 과정에서의 시간 소모일까? HashMap을 배열로 바꿔 확인해보니 정답이었다. → Sol3

고찰

Solution

1. HashMap에 값 넣기

   • nums 순회 HashMap에 값 넣기
   • 1부터 HashMap에 없는 값 찾기

   class Solution {
       fun firstMissingPositive(nums: IntArray): Int {
           val list = HashMap<Int, Boolean>()
           // Map에 집어 넣기
           for (num in nums) {
               if (num > 0) list[num] = true
           }
           // 1부터 존재하는지 확인
           for (i in 1..100001) {
               if (list[i] == null) return i
           }
           return 1
       }
   }
   

   시간 복잡도: nums 순회 + 양의 정수 순회 = n

   

2. Cyclic Sort

   • 배열 index = 0 부터 순회

   • 배열[index] ≠ index인 경우, 배열[index]의 값을 해당 값을 인덱스 칸과 스왑

     ex) 0, 1, 3, 7. 8 → 0, 1, 7, 3, 8

   • 배열[index]의 값이 범위(nums.size)를 벗어나는 경우는 무시하고 통과

   class Solution {
       fun firstMissingPositive(nums: IntArray): Int {
           val sorted = Array<Int>(nums.size + 1){0}
           nums.forEachIndexed { index, i -> sorted[index + 1] = i }
           var idx = 1
           while (idx < sorted.size) {
               if (sorted[idx] != idx && sorted[idx] < sorted.size && sorted[idx] > 0 && sorted[sorted[idx]] != sorted[idx]) {
                   sorted[sorted[idx]] = sorted[idx].also { sorted[idx] = sorted[sorted[idx]] }
               } else {
                   idx++
               }
           }
           for (i in 1 until sorted.size) {
               if (sorted[i] != i) return i
           }
           return sorted.size
       }
   }
   

   시간 복잡도: 배열 순회 + 배열 순회 = n

   

   ⁉ 이름은 있어보이지만 결국 1번과의 차이는 Map → Array

3. Sol1의 Map을 배열로 변경

   Sol1에서 정수를 키 값으로 해당 정수를 저장하기 때문에 배열이 더 자연스러움

   class Solution {
       fun firstMissingPositive(nums: IntArray): Int {
           val list = Array<Int>(nums.size + 2) {0}
           // Map에 집어 넣기
           for (num in nums) {
               if (num > 0 && num <= nums.size) list[num] = num
           }
           // 1부터 존재하는지 확인
           for (i in 1..nums.size + 1) {
               if (list[i] != i) return i
           }
           return 1
       }
   }
   

   시간 복잡도: 배열 순회 + 배열 순회 = n

   

Point

1. 배열에서 없는 값 찾기 / 반복되는 값 찾기 ⇒ Cyclic Sort
2. n이 커질수록 배열이 조회에서 가장 빠르기 때문에 배열을 Map처럼 쓰는 것이 가장 좋음 → hashMap vs Array 속도 비교