[리트코드] 41. First Missing Positive

---

[문제 간단 설명]

시간복잡도 O(n) 이하로, 정렬되지 않은 정수 배열 nums가 주어졌을 때, nums에 존재하지 않는 가장 작은 양의 정수 구하기

 

[풀이 방법]

1. 주어진 nums배열 정렬

2. answer = 1로 선언 및 초기화

3. nums의 원소값들을 반복하며 answer과 값이 같을 경우 answer을 1증가,  양수이고 answer보다 큰 값을 가질 경우 반복문을 빠져나감

4. answer 반환

 

* 3의 조건 중 "양수이고 answer보다 큰 값을 가질 경우 반복문을 빠져나감"의 조건이 없어도 정답을 반환한다. 하지만 [1, 2, 3, 5, 6, 7]과 같은 상황에서 해당 조건을 추가하면 전체를 반복하지 않고 정답을 찾을 수 있기 때문에 시간측면에서 유리하다.

 

[코드_Java]

import java.util.Arrays;

class Solution {
    public int firstMissingPositive(int[] nums) {
        int answer = 1;
        
        Arrays.sort(nums);
        for(int n: nums) {
            if(n == answer) answer++;
            else if(n > 0 && n > answer) break;
        }
        
        return answer;
    }
}

 

[코드_Python]

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        answer = 1
        
        nums.sort()
        for n in nums:
            if n == answer: answer += 1
            elif n > 0 and n > answer: break
        
        return answer

 

 

[아쉬운 점]

정렬메서드를 사용하지 않고 시간복잡도 O(n) 이하로 해결할 수 있는 방법이 있을것같다!!!! 꼭 다시 생각해봐야지 :)

---

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

First Missing Positive - LeetCode