[Programmers] #181858 - 무작위로 K개의 수 뽑기 [Java][C++][Python]

문제 링크

---

1. 아이디어

랜덤으로 서로 다른 k개의 수를 저장한 배열을 만들어야 한다. 길이 k의 배열은 정수 배열 arr에서 앞에서부터 순서대로 원소들을 보며 이미 담은 적이 있으면 넘어가고 처음보는 원소면 담는 과정을 k개의 서로 다른 원소를 담을 때까지 반복하면 조건에 맞는 배열을 구할 수 있다. 이때 k개의 서로 다른 원소가 존재하지 않을 수 있으므로 미리 -1로 초기화한 배열에 순서대로 담다가 arr의 마지막 원소까지 전부 확인했거나 k를 다 담았을 경우 종료했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N + K)$

($N$ = arr의 길이, $K$ = k)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int k) {
        boolean[] seen = new boolean[1 + 100000];
        int[] ans = new int[k];
        Arrays.fill(ans, -1);

        int idx = 0;
        for (int x : arr) {
            if (seen[x]) continue;
            ans[idx++] = x;
            seen[x] = true;

            if (idx == k) break;
        }

        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

bool seen[1 + 100000];

vector<int> solution(vector<int> arr, int k) {
    vector<int> ans(k, -1);

    int idx = 0;
    for (int x : arr) {
        if (seen[x]) continue;
        ans[idx++] = x;
        seen[x] = true;

        if (idx == k) break;
    }

    return ans;
}

def solution(arr, k):
    seen = set()
    ans = [-1] * k

    idx = 0
    for x in arr:
        if x in seen:
            continue
        ans[idx] = x
        seen.add(x)
        idx += 1

        if idx == k:
            break

    return ans

---