(C++) - LeetCode (easy) 1539. Kth Missing Positive Number

https://leetcode.com/problems/kth-missing-positive-number/description/

Kth Missing Positive Number - LeetCode

전수조사 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

원소 최대 개수가 1000이므로 vector cnt를 선언해 해결 가능합니다. arr의 원소를 순회하며 cnt의 index는 수, cnt[index]는 빈도 수를 저장해줍니다.

📔 풀이과정

1. arr 길이가 1000 원소의 최갯값이 1000이므로 1 ~ 1000이 strict하게 찬 arr을 생각하면 k가 1000일 때 1001 ~ 2000까지의 범위가 missing array의 원소들이라는 것을 알 수 있습니다.

2. 따라서 1 ~ 2000의 범위를 돌며 cnt에 i원소가 있는지 확인해 없으면 missArr에 원소를 push_back합니다.

📔 정답 출력 | 반환

missArr[k-1]을 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        unordered_map <int, int> arrMap;
        for(auto a : arr) {
            arrMap[a] = 1;
        }
        vector <int> missArr; 
        for(int i = 1; i <= 2000; i++) {
            if(!arrMap.count(i)) {
                missArr.push_back(i);
            }
        }
        return missArr[k-1];
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.