문제 이해하기
n_rows개의 행과 n_cols개의 열을 가진 이진 행렬이 있다고 가정해 보겠습니다. 모든 값은 처음에 0으로 초기화되어 있으며, 여기서 두 가지 함수를 구현해야 합니다.
- flip(): 값이 0인 위치 하나를 균등한 확률로 무작위로 골라 1로 바꾸고, 그 좌표 [row_id, col_id]를 반환합니다.
- reset(): 행렬의 모든 값을 다시 0으로 되돌립니다.
핵심 요구 사항은 시스템의 난수 생성 함수 호출 횟수를 최소화하면서 시간 복잡도와 공간 복잡도까지 최적화하는 것입니다.
예를 들어 2×3 크기의 행렬에서 flip()을 네 번 호출하면 [0,1], [1,2], [1,0], [1,1] 같은 결과가 나올 수 있습니다. 무작위 선택이므로 실행할 때마다 반환되는 순서는 달라질 수 있습니다.
풀이 접근 방법
이 문제는 Fisher-Yates 셔플 아이디어를 해시 맵으로 응용하면 효율적으로 해결할 수 있습니다. 아직 선택되지 않은 셀의 개수(size)를 줄여가면서, 이미 선택된 인덱스를 맵에 기록해 실제 배열에서 두 원소를 맞바꾼 것과 같은 효과를 내는 방식입니다. 단계별로 정리하면 다음과 같습니다.
holes라는 이름의 해시 맵을 준비합니다.- 생성자에서 난수 생성기를 초기화하고, n := 행의 개수, m := 열의 개수로 설정한 뒤 size := n × m 으로 둡니다.
- flip() 메서드에서 다음을 수행합니다.
- id := 난수 mod size로 정하고, size를 1 감소시킨 후 rid := id로 저장합니다.
- id가 holes에 이미 존재하면 id := holes[id]로 치환합니다.
- holes[rid] := size가 holes에 있으면 holes[size], 없으면 size로 설정합니다.
- (id / m, id mod m) 쌍을 반환합니다. 각각 행 인덱스와 열 인덱스에 해당합니다.
- reset() 메서드에서 size := n × m 으로 되돌리고 holes 맵을 비웁니다.
이 방식의 장점은 행렬 전체를 2차원 배열로 유지할 필요가 없다는 점입니다. 해시 맵에는 실제로 선택된 셀 정보만 저장되므로 공간 사용량은 flip() 호출 횟수에 비례하고, flip() 한 번의 평균 시간 복잡도는 O(1)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
unordered_map<int, int> holes;
int n;
int m;
int size;
Solution(int n_rows, int n_cols) {
srand(time(NULL));
n = n_rows;
m = n_cols;
size = n * m;
}
vector<int> flip() {
int id = rand() % size;
size--;
int rid = id;
if (holes.count(id)) {
id = holes[id];
}
holes[rid] = holes.count(size) ? holes[size] : size;
return {id / m, id % m};
}
void reset() {
size = n * m;
holes.clear();
}
};
main() {
Solution ob(2, 2);
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
}
입력
생성자를 2×2 크기로 초기화한 뒤 flip()을 네 번 호출합니다.
출력
[1, 1] [0, 0] [1, 0] [0, 1]