선거에서 i번째 표가 times[i] 시점에 persons[i] 후보에게投되었다고 가정해 보겠습니다. 우리는 다음과 같은 쿼리 함수를 구현해야 합니다.
TopVotedCandidate.q(int t) — t 시점에 선거를 리드하고 있던 후보의 번호를 반환합니다. 정확히 t 시점에投된 표도 쿼리 결과에 포함되며, 동률이 발생할 경우 동률 후보 중 가장 최근에 표를 받은 후보가 승자가 됩니다.
동작 예시
TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30])으로 클래스를 초기화한 뒤, q(3), q(12), q(25), q(15), q(24), q(8) 순서로 호출하면 결과는 각각 [0, 1, 1, 0, 0, 1]이 됩니다.
- t = 3까지의 표는 [0]이므로 후보 0이 리드하고 있습니다.
- t = 12까지의 표는 [0,1,1]이므로 후보 1이 리드하고 있습니다.
- t = 25까지의 표는 [0,1,1,0,0,1]이며, 동률 처리 규칙(가장 최근 표 우선)에 따라 후보 1이 리드합니다.
- 이후 t = 15, 24, 8에 대한 세 번의 쿼리도 같은 방식으로 계산됩니다.
풀이 접근 방법
- 두 개의 맵(map) m과 count를 생성합니다.
- 생성자에서 다음 작업을 수행합니다.
- lead := -1로 초기화합니다.
- i를 0부터 times 배열의 크기까지 반복합니다.
- x := times[i]
- count[persons[i]] 값을 1 증가시킵니다.
- count[lead] <= count[persons[i]]라면 lead := persons[i]로 갱신한 뒤 m[x] := lead를 저장하고, 그렇지 않으면 m[x] := lead만 저장합니다.
- q() 메서드는 다음과 같이 동작합니다.
- m에서 t의 상한(upper bound) 바로 앞 원소를 찾아 해당 값을 반환합니다. 즉, t 이하 시점 중 가장 최근에 기록된 리더를 돌려줍니다.
핵심 아이디어는 전처리 단계에서 모든 투표 시점별 리더를 미리 계산해 맵에 저장해 두는 것입니다. 조건 비교에 <=(이하)를 사용하기 때문에 득표 수가 같을 때 새로 표를 받은 후보가 리더를 넘겨받게 되며, 이것이 곧 '동률일 경우 최근 표 우선' 규칙을 자연스럽게 구현합니다. 또한 std::map은 키가 오름차순으로 정렬되므로, upper_bound(t)가 반환하는 반복자(키가 t보다 큰 첫 원소)에서 1을 감소시키면 키가 t 이하인 마지막 원소, 즉 원하는 시점의 리더를 즉시 얻을 수 있습니다.
아래 구현을 통해 더 자세히 살펴보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class TopVotedCandidate {
public:
map <int, int> m;
map <int, int> count;
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
int lead = -1;
for(int i = 0; i < times.size(); i++){
int x = times[i];
count[persons[i]]++;
if(count[lead] <= count[persons[i]]){
lead = persons[i];
m[x] = lead;
}else{
m[x] = lead;
}
}
}
int q(int t) {
return ((--m.upper_bound(t)) -> second);
}
};
int main(){
vector<int> v1 = {0,1,1,0,0,1,0}, v2 = {0,5,10,15,20,25,30};
TopVotedCandidate ob(v1, v2);
cout << (ob.q(3)) << endl;
cout << (ob.q(12)) << endl;
cout << (ob.q(25)) << endl;
cout << (ob.q(15)) << endl;
cout << (ob.q(24)) << endl;
cout << (ob.q(8)) << endl;
}입력
[0,1,1,0,0,1,0]과 [0,5,10,15,20,25,30]으로 클래스를 초기화하고, 다음과 같이 q() 메서드를 호출합니다: q(3) q(12) q(25) q(15) q(24) q(8)
출력
0 1 1 0 0 1
복잡도 분석
생성자에서 n개의 표를 한 번씩 처리하며 각 삽입이 맵 연산이므로 전처리 단계의 시간 복잡도는 O(n log n)입니다. q(t) 호출은 std::map의 upper_bound 탐색을 사용하므로 쿼리당 O(log n)의 시간이 걸립니다. 덕분에 동일한 데이터에 대해 쿼리가 여러 번 반복되는 상황에서도 매우 효율적으로 동작합니다.