0-4. 무작위로 K개의 수 뽑기 ( 배열의 중복된 수 제거하기 )

1. 문제

랜덤으로 서로 다른 k개의 수를 저장한 배열을 만드려고 합니다. 적절한 방법이 떠오르지 않기 때문에 일정한 범위 내에서 무작위로 수를 뽑은 후, 지금까지 나온적이 없는 수이면 배열 맨 뒤에 추가하는 방식으로 만들기로 합니다.

이미 어떤 수가 무작위로 주어질지 알고 있다고 가정하고, 실제 만들어질 길이 k의 배열을 예상해봅시다.

정수 배열 arr가 주어집니다. 문제에서의 무작위의 수는 arr에 저장된 순서대로 주어질 예정이라고 했을 때, 완성될 배열을 return 하는 solution 함수를 완성해 주세요.

단, 완성될 배열의 길이가 k보다 작으면 나머지 값을 전부 -1로 채워서 return 합니다.

---

제한사항

• 1 ≤ arr의 길이 ≤ 100,000
  • 0 ≤ arr의 원소 ≤ 100,000
• 1 ≤ k ≤ 1,000

---

 

입출력 예

[0, 1, 1, 2, 2, 3]	3	[0, 1, 2]
[0, 1, 1, 1, 1]	4	[0, 1, -1, -1]

 

2. 코드

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;


vector<int> solution(vector<int> arr, int k) {
    vector<int> answer;

    // 중복을 제거한 순서대로 저장하기 위한 벡터
    vector<int> temp;

    // 중복을 제거하며 temp에 저장
    unordered_map<int, bool> m1;
    for (int num : arr)
    {
        if (!m1[num]) // m1에 값이 없다면(false 라면)
        {
            m1[num] = true;
            temp.push_back(num);
        }
    }

    // k개만큼 값 선택하기
    for (int i = 0; i < k; i++)
    {
        if (i < temp.size())
        {
            answer.push_back(temp[i]);
        }
        else
        {
            answer.push_back(-1);
        }
    }

    return answer;
}

 

3. 풀이

주어진 배열 arr에서 k개의 중복되지 않은 수를 뽑는다. 만약 k개를 미달할 경우 나머지 수는 -1로 저장한다.

배열이 랜덤으로 제시되었기 때문에 자동으로 정렬되는 map을 이용하지 않고 unordered_map을 사용한다.

arr의 각 숫자를 순회하며 m1의 key 값에 각 숫자인 num을 저장하고, value 값을 true로 바꾼다.

이후, m1에 값이 이미 존재하기 때문에 temp 배열에 숫자를 중복적으로 저장하지 않게 된다.

마지막으로 temp를 k만큼 순회해주고, 남은 만큼을 -1로 채우면 된다.