LeetCode 41번 - First Missing Positive

leetcode.com/problems/first-missing-positive/

First Missing Positive - LeetCode

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
       set<int> s(nums.begin(),nums.end());
       int size = nums.size();
       int result = 1;
       for(result = 1; result <= size; result++){
           if(!s.count(result)){
               return result;
           }
       }
        return result;
    }    
};
    

 

처음 내가 접근한 방법은 일반적으로 처음 떠오르는 방법이였다. 

리스트를 만들고 하나 하나 비교해서 케이스 별로 찾는 방법을 떠 올렸다 코드는 이것보다 약 5배는 길고 시간도 많이 걸렸다. 

하지만, 다른 방법이 떠오르지 않았다. 

인터넷 검색을 통해 힌트를 얻으니, count라는 방법을 사용할 수 있다는 것을 알게되고 다시 짜보았다. 

1부터 시작해서 검사를 하면서, count가 0인것, 즉 리스트에 없는 가장 작은 양의 정수를 찾았을때 return 하는 것이다. 

여기서 더욱 빠르게 하는것은 set데신 unordered set을 사용하고, result++ 데신 전위 증가 연산자를 사용하는것이고, 그렇게 하면 더 빠르고 좋은 결과를 얻을 수 있다.