문제 개요
구간 [0, N)에 속하는 고유한 정수들로 이루어진 블랙리스트 B가 있다고 가정해 보겠습니다. 이때 블랙리스트에 포함되지 않은 숫자 중 하나를 균등한 확률로 반환하는 무작위 선택 함수를 정의해야 합니다. 또한 random() 함수의 호출 횟수를 줄여 성능을 최적화하는 것이 핵심 목표입니다.
해결 전략: 맵을 활용한 매핑 기법
이 문제는 맵(map)을 활용한 매핑 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 블랙리스트를 제외한 실제 선택 가능한 숫자의 개수를 M이라고 합니다.
- pick()이 호출되면 [0, M) 범위에서 난수를 단 한 번만 생성합니다.
- 생성된 숫자가 블랙리스트에 있다면, 미리 구축해 둔 맵을 통해 유효한 숫자로 치환하여 반환합니다.
알고리즘 단계
- 정수 쌍을 저장할 맵 하나를 정의합니다.
- N과 배열 v로 객체를 초기화합니다.
- i := 0부터 시작해 i가 v의 크기보다 작은 동안 i를 1씩 증가시키며 반복합니다.
- 만약 v[i] < N이면, m[v[i]] := -1로 설정합니다. - M := N - m의 크기로 계산합니다. (M은 실제 선택 가능한 숫자의 개수)
- n := v의 크기를 저장합니다.
- 다시 i := 0부터 v의 크기까지 반복하며 다음을 수행합니다.
- 만약 v[i] < M이면:
- N을 1 감소시킵니다.
- N이 맵 m에 존재하는 동안 N을 계속 1씩 감소시킵니다.
- m[v[i]] := N으로 설정해 블랙리스트 숫자를 유효한 숫자와 연결합니다. - pick() 함수를 정의합니다.
- x := 난수 mod M으로 설정합니다.
- x가 맵 m에 존재하면 m[x]를, 존재하지 않으면 x 그대로 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int M;
map <int,int> m;
Solution(int N, vector<int>& v) {
for(int i = 0; i < v.size(); i++){
if(v[i] < N) m[v[i]] = -1;
}
M = N - (int)(m.size());
int n = v.size();
for(int i = 0; i < v.size(); i++){
if(v[i] < M){
while(m.count(--N));
m[v[i]] = N;
}
}
}
int pick() {
int x = rand() % M;
return m.count(x)? m[x] : x;
}
};
main(){
vector<int> v = {2};
Solution ob(4,v);
cout << (ob.pick()) << endl;
cout << (ob.pick()) << endl;
cout << (ob.pick()) << endl;
}
입력 및 출력 예시
입력
N = 4, 배열 = [2]
출력
1 1 0
동작 원리 살펴보기
예제에서 N = 4이고 블랙리스트는 {2}입니다. 전체 후보 구간은 {0, 1, 2, 3}이지만 2가 제외되므로, 실제로 선택 가능한 숫자는 {0, 1, 3} 세 개입니다. 따라서 M = 4 - 1 = 3이 됩니다.
생성자의 두 번째 반복문은 블랙리스트 값 중 M 미만인 값(여기서는 2)을 찾아, 구간 끝쪽의 유효한 숫자인 3과 매핑합니다. 그 결과 m[2] = 3이 저장됩니다.
pick()이 호출되면 rand() % M을 통해 0, 1, 2 중 하나가 뽑힙니다. 만약 2가 나오면 맵 조회를 거쳐 3으로 치환되어 반환됩니다. 덕분에 random() 호출은 단 한 번만 발생하고, 모든 유효 숫자는 동일한 확률로 선택됩니다.
복잡도 분석
생성자 초기화에는 O(B log B) 시간이 소요됩니다(B는 블랙리스트의 크기이며, 맵 연산 비용 포함). 반면 pick() 호출은 O(log B)에 처리되므로, 매번 블랙리스트와 대조하며 재추첨하는 나이브한 방식보다 훨씬 효율적입니다.