[JAVA/LeetCode] Top 100 Liked Question: 41. First Missing Positive

👀 문제

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

👊 도전

1. 설계

1. 숫자 개수+1개의 boolean 배열을 만든다.
2. 인덱스를 숫자로 생각하고, 해당 숫자가 존재하면 true를 저장한다.
3. 인덱스 1부터 순회하며 false인 인덱스를 리턴한다.
4. 모두 true라면 마지막 숫자+1을 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int firstMissingPositive(int[] nums) {
        int size=nums.length;
        boolean[] number=new boolean[size+1];
        
        for(int num:nums){
            if(num<1 || num>size) continue; // 음수거나 배열 범위를 벗어나는 숫자는 패스
            number[num]=true;
        }
        
        for(int i=1;i<=size;i++){
            if(!number[i]) return i; // 없는 숫자를 리턴
        }
        
        return size+1; // 숫자가 다 존재한다면 마지막 숫자 다음을 리턴
    }
}

3. 결과

🤟 성공 🤟
처음에는 오름차순 정렬 후, 앞에서부터 체크하며 +1이 아니면 없는 값을 리턴하게 했는데, 예외가 많아서 다른 사람의 코드를 참고했다.
배열에 중복값이 있을 수도 있다는 것을 생각해야 한다.

4. 설명

1. boolean 배열을 만든다
   • 배열은 1부터 nums 개수만큼 사용한다. 따라서 nums.length+1이다.
   • 인덱스를 숫자라고 가정하고, 배열에 해당 숫자가 있으면 true로 바꾼다.
2. boolean 배열을 체크하며 없는 숫자를 찾는다
   • 0은 사용하지 않으므로 패스한다.
   • false인 값이 나오면, 해당 인덱스를 리턴한다.
   • [2,3,4]인 경우 boolean 배열에는 숫자 1,2,3을 저장할 수 있는데, 1 자리에 false이므로 바로 1을 리턴한다.
   • [1,3,4]인 경우, boolean 배열에는 1,2,3을 저장할 수 있는데, 2가 false이므로 2를 리턴한다.
   • [1,2]인 경우에는 boolean에 1,2를 저장할 수 있고, 둘 다 true가 들어가므로 for문에서 리턴하지 않는다. 마지막 줄에서 2(배열 사이즈)+1로 다음 숫자 3을 리턴한다.

👏 해결 완료!